COMPUTABILITA'

La computabilità, o calcolabilità, studia le funzioni (e i problemi) che possono essere calcolate (ovvero risolti) mediante un procedimento meccanico, prescindendo dalla quantità, purché finita, di risorse necessarie di spazio/tempo.
L’obiettivo primario è dunque la formalizzazione della nozione di algoritmo, mediante modelli di calcolo effettivi. Come modello di calcolo primario sarà adottato quello delle macchine a registri illimitati (URM: Unlimited Register Machines), ma verranno anche presentati velocemente altri modelli di calcolo, quale quello delle macchine di Turing e quello delle funzioni ricorsive generali. Tali modelli (e anche tutti gli altri sinora proposti) risultano essere equivalenti in termini di potenza, nel senso che una funzione è calcolabile in uno dei modelli se e solo se lo è in tutti gli altri. Ciò fa ritenere che il modello di calcolo delle macchine a registri illimitati catturi perfettamente il concetto astratto di algoritmo (tesi di Church-Turing).
Così come una funzione si dice calcolabile se tutti i suoi valori possono essere calcolati algoritmicamente, un problema o predicato si dirà decidibile se può essere risolto mediante un algoritmo.
Utilizzando una enumerazione effettiva delle macchine URM (ispirata alla codifica di Gödel) ed il metodo diagonale di Cantor, saranno esibiti esempi di funzioni non calcolabili e di predicati indecidibili. Questi ultimi, in particolare, comprendono parecchi problemi riguardanti l’esito dell’esecuzione di programmi di calcolatori.
La nozione di decidibilità sarà generalizzata a quella di semi-decidibilità e saranno fornite tecniche per verificare se un dato predicato è (semi-)decidibile oppure no (tecnica della riduzione, teoremi di Rice e di Rice-Shapiro, teorema s-m-n).

Lezioni frontali

- Elementi di matematica discreta
- Concetto intuitivo di algoritmo
- Elementi di logica matematica

Per una piena comprensione degli argomenti del corso e delle tecniche risolutive illustrate, la frequenza delle lezioni è fortemente consigliata.

Funzioni calcolabili: Algoritmi, procedure effettive. Modello URM: Unlimited Register Machines. Funzioni URM-calcolabili. Predicati e problemi decidibili. Calcolabilità su altri domini.

Generazione di funzioni URM-calcolabili: Funzioni calcolabili di base. Composizione. Ricorsione. Minimalizzazione.

Tesi di Church-Turing: Altri approcci alla computabilità. Funzioni ricorsive primitive e ricorsive generali. Macchine di Turing. (Sistemi di Post e di Markov)

Enumerazione delle funzioni calcolabili: Enumerazione dei programmi URM. Metodo diagonale. Teorema s-m-n.

Programmi universali: Funzioni e programmi universali (e applicazioni). Operazioni effettive su funzioni calcolabili.

Decidibilità, indecidibilità e semi-decidibilità: Problemi indecidibili in computabilità e in altre aree della matematica. Teorema di Rice. Problemi semi-decidibili.

Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice-Shapiro.

1) N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge - UK, 1986. [Testo principale]

2) M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994. [Lettura consigliata]

L’esame finale è essenzialmente scritto. La verbalizzazione sarà preceduta da una breve discussione sul compito scritto e, nei casi dubbi, da una breve verifica orale.

http://www.dmi.unict.it/~cantone/ESAMI/ESAMI_COMPUTABILITA/Cmp-sample-2016.pdf