B020989 - CALCOLABILITA' E LOGICA

ITALIANO

Introduzione alla teoria della ricorsività e ai teoremi limitativi della logica (incompletezza, indecidibilità, indefinibilità).

a) materiale fornito dal docente;
b) P. Smith. An introduction to Goedel's theorems. CUP 2007

(i) Conoscenza e capacità di comprensione.
Conoscenza delle principali tematiche e metodologie relative alla teoria della ricorsività e ai teoremi limitativi. Capacità di comprendere e collegare problemi in questi ambiti di ricerca.
(ii) Capacità di applicare conoscenza e comprensione. Applicazione delle conoscenze e capacità di comprensione acquisite nel corso alla trattazione di problemi specifici nell'ambito della logica, attraverso esercizi proposti.
(iii) Autonomia di giudizio. Approfondimento critico delle conoscenze acquisite nel corso mediante la lettura e lo studio autonomo di contributi scientifici (articoli, monografie).
(iv) Abilità comunicative. Esporre problemi/soluzioni di problemi/teorie/argomenti/dimostrazioni in modo comunicativamente e scientificamente appropriato, con padronanza della terminologia tecnica.

Il corso propedeutico da 12 CFU di Logica (CdS triennale in Filosofia), o conoscenze equivalenti (in questo caso parlare con il docente prima dell'iscrizione al corso).

Lezioni frontali integrate da esercitazioni guidate dal docente.

Il corso utilizza la piattaforma MOODLE (http://e-l.unifi.it/). E' richiesta l'iscrizione online al corso entro la prima settimana di lezioni.
I materiali per il corso (dispense, sintesi delle lezioni, esercizi, ecc.) saranno resi disponibili solo sulla piattaforma Moodle.
Si ricorda che è richiesta una frequenza obbligatoria per almeno i 2/3 delle lezioni.
Non sono previste modalità di esame da non frequentante se non per gli studenti con iscrizione part-time (che devono prendere contatto con il docente all'inizio del corso per concordare un programma specifico).

L'esame consiste in una prova orale (durata: 45 minuti circa), articolata in due domande sulla prima parte del programma (calcolabilità/ricorsività) e due domande sulla seconda parte del programma (teoremi limitativi).
La prova mira a verificare:
(i) la conoscenza e la comprensione delle nozioni teoriche fondamentali del programma;
(ii) l'acquisizione della capacità di applicare quanto appreso a esercizi/problemi che saranno proposti durante il colloquio, in analogia con quelli svolti nel corso delle esercitazioni.
Alla graduazione analitica della prestazione dello studente concorrerà anche la valutazione della capacità espositiva e in particolare della precisione nell'uso del linguaggio "tecnico" della disciplina

Computabilità.
Funzioni ricorsive primitive; mu-ricorsività.
Teorema della forma normale di Kleene
La teoria PA e importanti sottoteorie.
Aritmetizzazione.
Rappresentabilità.
Teorema di diagonalizzazione.
Teoremi di incompletezza di Goedel. Teorema di indecidibilità di Church. Teorema di Tarski