|
|
|
T5: Calcolo, simboli e intelligenza,
Prima parte: Calcolo e simboli.
Dopo aver introdotto il contesto di riferimento, leggeremo assieme "On computable numbers", il lavoro scientifico del 1936 nel quale Turing indaga la nozione di "far di conto" e introduce un modello astratto di calcolo che costituisce la base teorica dei moderni calcolatori. Scopriremo quindi la nozione di "numero reale calcolabile" e l'esistenza di numeri (e problemi) che non possono essere calcolati (o risolti) da nessun programma per calcolatore. Discuteremo infine il ruolo centrale dell'aspetto linguistico nella descrizione del calcolo..
Programma :
- i contributi scientifici di A.M. Turing;
- il contesto di riferimento di "On computable numbers";
- lo Entscheidungsproblem;
- lettura e commento delle sezioni: 1-3,5,6,8,9,11(solo accennata);
- altri formalismi per la calcolabilitą: le funzioni ricorsive di Kleene;
- la tesi di Church.
Materiale didattico e trasparenze:
On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. Lond. Math. Soc. (2) 42 pp. 230-265 (1936).
Trasparenze usate per alcune lezioni: prima lezione; terza lezione; quarta lezione.
Esame:
Piccoli saggi scritti (un tema per ognuna delle tre parti del curriculum).
Prerequisiti:
Aritmetica elementare. Concetto di funzione. Insiemi.
Capacità richieste:
Buona capacità di astrazione; manipolazione simbolica.