a) materiale fornito dal docente;
b) P. Smith. An introduction to Goedel's theorems. CUP 2007
Obiettivi Formativi
Il corso si propone di introdurre gli studenti alle basi della teoria della computabilità e ai fondamentali risultati limitativi di Goedel, Church e Tarski
Prerequisiti
Un corso introduttivo di logica
Metodi Didattici
lezioni frontali e esercitazioni
Altre Informazioni
Il corso utilizza la piattaforma MOODLE (http://e-l.unifi.it/). E' richiesta l'iscrizione online al corso entro la prima settimana di lezioni.
Modalità di verifica apprendimento
esame orale
Programma del corso
Funzioni ricorsive primitive; mu-ricorsività.
La teoria PA e importanti sottoteorie.
Aritmetizzazione.
Rappresentabilità.
Teorema di diagonalizzazione.
Teoremi di incompletezza di Goedel. Teorema di indecidibilità di Church. Teorema di Tarski