MODULO DI COMPUTABILITÀ
Programma del corso, introduzione, macchine URM,
computazioni, funzioni calcolabili, parziale e totale correttezza
di programmi URM
(Agg. 08/03/14) |
Decidibilità di predicati,
calcolabilità su altri domini, funzioni di base, composizione di
funzioni
(Agg. 08/03/14) |
Ricorsione, definizione per casi, somme e prodotti
limitati, minimalizzazione limitata, funzioni primitive ricorsive
(Agg. 31/03/12) |
Notazione "uparrow" di Knuth, funzione di
Ackermann, calcolabilità della funzione di Ackermann, Loop
Programs, Bounding Theorem, dimostrazione che la funzione di
Ackermann non è primitiva ricorsiva
(Agg. 31/03/12) |
Minimalizzazione
(Agg. 5/04/11) |
Altri approcci alla calcolabilità,
funzioni parziali ricorsive, funzioni μ-ricorsive, equivalenza
tra funzioni URM-calcolabili e funzioni parziali ricorsive,
relazione tra funzioni μ-ricorsive e funzioni parziali
ricorsive, tesi di Church
(Agg. 5/04/11) |
Enumerazione delle funzioni calcolabili, metodo
diagonale di Cantor, teorema di parametrizzazione
(s-m-n)
(Agg. 7/04/11) |
Programmi
universali, forma normale di Kleene, indecidibilità del
problema "φx è totale", esistenza di
una funzione calcolabile totale non primitiva ricorsiva mediante
diagonalizzazione, operazioni
effettive su funzioni calcolabili e loro domini e codomini
(Agg. 16/04/12) |
Definizione per casi con funzioni calcolabili
(anche parziali)
(Agg. 24/04/12) |
Problemi indecidibili, tecnica della riduzione,
teorema di Rice, indecidibilità in altri domini, predicati
parzialmente decidibili
(Agg. 28/04/10) |
Insiemi ricorsivamente enumerabili, varie
caratterizzazioni, teorema di Rice-Shapiro
(Agg. 12/05/11) |
|