Macchine a registri
Funzioni ricorsive parziali
Predicati decidibili e semidecidibili
Tesi di Church Programmi universali
Problema della fermata
Riducibilità tra problemi
Equivalenza di programmi Indecidibilità del calcolo dei predicati Gerarchia aritmetica di complessità
Teoremi di incompletezza di Gödel
Funzionali calcolabili
Semantica al punto fisso dei programmi
Secondo teorema di ricursione
Complessità di calcolo