Come per tutti i curricula del Collegio, non sono previste propedeuticità tra i vari anni di corso, per consentire allo studente l'inserimento in uno qualunque dei suoi tre anni.

Programma preliminare del corso

Obiettivi: Il corso risponderà alla domanda se esistano limitazioni assolute (cioè non dipendenti da fattori tecnologici) ai problemi risolubili da un calcolatore.

Dopo aver discusso la nozione intuitiva di calcolabilità, introdurremo alcuni modelli formali di tale nozione (la macchina di Turing, la Macchina a registri illimitati, ecc.) e mostreremo che tutti questi modelli sono in grado di calcolare esattamente la stessa classe di funzioni (le funzioni ricorsive di Kleene).

Potremo ora rispondere in modo affermativo alla domanda iniziale: esistono funzioni (problemi) che non possono essere calcolate (risolti) da nessun modello di calcolo (da nessun calcolatore). Indagheremo quindi le relazioni tra questi modelli di calcolo e i calcolatori (computer), attraverso la nozione di macchina universale.

Concluderemo con alcune nozioni e risultati importanti della teoria della calcolabilità e delle sue applicazioni alla logica matematica.

Modalità d'esame: tesina su uno degli argomenti proposti qui, oppure su tema proposto dallo studente.

Materiale del corso: Sono a disposizione le note (trasparenze) usate per il corso (solo la prima, seconda e sesta lezione): trasparenze.