- Lucidi delle lezioni
Programma del corso, introduzione, macchine URM,
computazioni, funzioni calcolabili
(Agg. 27/02/16) |
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) |
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. 20/04/16) |
Problemi indecidibili, tecnica della riduzione,
teorema di Rice, indecidibilità in altri domini, predicati
parzialmente decidibili
(Agg. 28/04/10) |
|