Introduzione, macchine URM,
computazioni, funzioni calcolabili, parziale e totale correttezza
di programmi URM
(Agg. 24/10/08) |
Decidibilità di predicati,
calcolabilità su altri domini, funzioni di base, composizione di
funzioni
(Agg. 24/10/08) |
Ricorsione, definizione per casi, somme e prodotti
limitati, minimalizzazione limitata
(Agg. 28/10/08) |
Minimalizzazione, funzione di
Ackermann
(Agg. 8/11/08) |
Altri approcci alla calcolabilità,
funzioni parziali ricorsive, funzioni μ-ricorsive, equivalenza
tra funzioni URM-calcolabili e funzioni parziali ricorsive,
macchine di Turing, tesi di Church
(Agg. 23/11/08) |
Enumerazione delle funzioni calcolabili, teorema
s-m-n
(Agg. 26/11/08) |
Programmi universali, forma normale di
Kleene, operazioni effettive su funzioni calcolabili
(Agg. 02/12/08) |
Problemi indecidibili, tecnica della riduzione,
teorema di Rice, indecidibilità in altri domini, predicati
parzialmente decidibili
(Agg. 30/12/08) |
Insiemi ricorsivamente enumerabili, varie
caratterizzazioni, teorema di Rice-Shapiro
(Agg. 29/01/08) |
|