Potenzialita\' e limiti teorici del concetto di calcolabilita\' e di metodo
assiomatico.
E\' caldamente suggerito, ma non strettamente necessario, aver sostenuto un esame di logica.
Esame scritto con 4-5 semplice esercizi. Eventuale seminario durante il
corso.
Italiano
Lezioni tradizionali, seminari su temi specifici svolti dagli studenti.
Sito web del corso.
Teoria della calcolabilita\' e teoremi di incompletezza.
Piu\' in dettaglio:
Spiegazione informale della nozione di funzione calcolabile. Macchine di Turing, macchine a registri, abaci, funzioni ricorsive. Loro equivalenza e tesi di Church. Insiemi decidibili e ricorsivamente enumerabili.
Sistema formale HA per la teoria dei numeri. Rappresentazione delle funzioni ricorsive. Aritmetizzazione della sintassi. Condizioni di Bernays-Hilbert-Loeb.
Primo e secondo teorema di incompletezza di Goedel. Indecidibilita\' della logica dei predicati. Conclusioni.