Sillabo dell'insegnamento

• A - Fondamenti
* CAL - Calcolabilita'
Enumerazione delle funzioni calcolabili. Esistenza di funzioni non calcolabili: il metodo della diagonalizzazione. Il teorema del parametro. Programmi universali.
* CAL - Calcolabilita'
Algoritmi ed il concetto di procedimento effettivo. Macchine a registri (URM). Funzioni parziali ricorsive (sostituzione, ricorsione, minimalizzazione). Equivalenze tra modelli di calcolo. Universalità dei modelli di calcolo. Tesi di Church.
* CAL - Calcolabilita'
Problemi decidibili, indecidibili e semidecidibili. Indecidibilità del problema della fermata. Metodo di riduzione. Esempi di altri problemi indecidibili.
* CAL - Calcolabilita'
Insiemi ricorsivi e ricorsivamente enumerabili. Teoremi di Rice e di Rice-Shapiro.
* CAL - Calcolabilita'
Funzionali. Definizioni ricorsive. Ordinamenti parziali, funzioni monotone e punti fissi. Funzionali ricorsivi. Relazione tra continuità e ricorsività. Il teorema di Myhill-Sheperdson. Primo teorema di ricorsione. Secondo teorema di ricorsione.