- Lucidi delle lezioni
Programma del corso, introduzione alla computabilità
(Agg. 22/03/18) |
Macchine di Turing
(Agg. 23/05/16) |
Unlimited Register Machines (URM), computazioni, funzioni calcolabili
(Agg. 22/03/18) |
Correttezza parziale e totale di programmi URM
(Agg. 22/03/18) |
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, non primitiva ricorsività della funzione di
Ackermann
(Agg. 10/04/18) |
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
|
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 parziali
(Agg. 15/05/18) |
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. 31/05/18) |
|