- Lucidi delle lezioni
Programma del corso, introduzione, macchine URM,
computazioni, funzioni calcolabili
(Agg. 28/02/17) |
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)
Macchine di Turing
(Agg. 23/05/16)
|
Enumerazione delle funzioni calcolabili, metodo
diagonale di Cantor, teorema di parametrizzazione
(s-m-n)
(Agg. 7/04/11) |
|