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
L’esame consiste in una prova orale (durata: 45 minuti circa) il cui scopo è accertare l’acquisizione (i) delle nozioni teoriche fondamentali del programma svolto a lezione, e della (ii) capacità di applicare quanto appreso a semplici esercizi/problemi che saranno proposti durante il colloquio, in analogia con quanto svolto nel corso delle esercitazioni. Alla graduazione analitica della prestazione dello studente concorrerà anche la valutazione della (iii) precisione nell’uso del linguaggio “tecnico” della disciplina.
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