Obiettivi del corso

Obiettivo di questo corso è quello di avvicinare lo studente ai temi classici della teoria della calcolabilità, ovvero alle fondamenta della teoria della computazione. Partendo dall'esame matematico del concetto di procedimento effettivo, si studieranno i limiti che tale nozione impone sulla classe delle funzioni effettivamente calcolabili da un algoritmo, con lo sviluppo di una teoria dell'indecidibilità e della ricorsione. Il corso dà luogo al conseguimento di 6 CFU.

Esiste un moodle del corso, dove si possono trovare le note informali delle lezioni. Si tratta di rielaborazioni del materiale del libro, che resta il riferimento principale.

Programma del corso

Il corso, della durata di 48 ore, svilupperà i seguenti temi:

1. Algoritmi ed il concetto di procedimento effettivo. Macchine a registri (URM). Funzioni parziali ricorsive (sostituzione, ricorsione, minimalizzazione). Modelli funzionali. Equivalenze tra modelli di calcolo. Universalità dei modelli di calcolo. Tesi di Church.
2. Enumerazione delle funzioni calcolabili. Esistenza di funzioni non calcolabili: il metodo della diagonalizzazione. Il teorema del parametro. Programmi universali.
3. Problemi decidibili, indecidibili e semidecidibili. Indecidibilità del problema della fermata. Metodo di riduzione. Esempi di altri problemi indecidibili.
4. Insiemi ricorsivi e ricorsivamente enumerabili. Insiemi produttivi, creativi e semplici. Teoremi di Rice e di Rice-Shapiro.
5. Funzionali. Definizioni ricorsive. Ordinamenti parziali, funzioni monotone e punti fissi. Funzionali ricorsivi. Relazione tra continuità e ricorsività. Il teorema di Myhill-Sheperdson. Primo teorema di ricorsione. Secondo teorema di ricorsione.

Segue una descrizione dettagliata degli argomenti trattati con una numerazione che si riferisce ai capitoli.paragrafi del testo adottato.

• Introduzione storica. Dalla logica alla computabilità all'informatica moderna. Organizzazione del corso. [Slide]
• Procedimento effettivo e funzione calcolabile. Caratteristiche di un algoritmo e di un modello di calcolo. Esistenza di funzioni non calcolabili (Prologue, 1.1, pag. 1-9).
• URM-calcolabilità. Classe C delle funzioni URM-calcolabili. Esempi di funzioni URM-calcolabili. Inultilità dell'istruzione di trasferimento (1.2, 1.3, pag. 9-22). (Curiosità: iURM: URM for iPhone, URM for Android)
• Esercizio: invarianza della classe delle funzioni calcolabili quando si sostituisce l'istruzione di trasferimento T(m,n) con l'istruzione di scambio T_s(m,n). Esercizio: cosa si calcola senza istruzioni di salto?
  
• Predicati decidibili (1.4, 22-23). Computabilità su altri domini (1.5, 23-24).
• Generazione di funzioni calcolabili: Funzioni di base (2.1). Composizione di programmi (2.2). Composizione generalizzata (2.3). Ricorsione primitiva (2.4). Minimalizzazione limitata (2.5).
• Codifica di coppie e k-ple. Considerazioni sulla ricorsione. Minimalizzazione (2.5). Esercizi su minimalizzazione.
• Altri approcci alla calcolabilità. Tesi di Church. Funzioni parziali ricorsive R. (3.1, 3.2, 3.3, 3.7)
  Implementazione in Haskell degli operatori per le funzioni parziali ricorsive e della funzione universale, fatta da uno studente degli anni precedenti.
• Funzioni primitive ricorsive PR. La funzione di Ackermann (totalità e cenni alla calcolabilità). (2.5) La Funzione di Ackermann non è primitiva ricorsiva.
  (Animazione della funzione di Ackermann)
• Enumerazione dei programmi URM (4.1)
• Enumerazione delle funzioni calcolabili. (4.2) Il metodo diagonale (4.3)
• Il teorema s-m-n di Kleene (4.4)
• Funzione universale (5.1, appendice del cap. 5)
• Esercizi e applicazioni della funzione universale (5.2, escluso il Teorema 2.2, e 5.3). Indecidibilità del problema della fermata (un video sul tema).
• Insiemi ricorsivi e riduzione (6.1 e 7.1)
• Teorema di Rice (6.1)
• Insiemi ricorsivamente enumerabili (7.2) e predicati semidecidibili (6.6)
• Teorema di Rice-Shapiro (6.6)
• Primo teorema di ricorsione (cenni - 10.1, 10.3)
• Secondo teorema di ricorsione (11.1, 11.2)

Orario del corso

Il corso fa parte del Corso di Laurea Magistrale in Informatica, Università di Padova, ed è collocato nel I semestre dell'Anno Accademico 2020/2021, con inizio il 28.09.2020, in Aula 1A/150 con il seguente orario:

• Lun (12:30 - 14:15)
• Mar (12:30 - 14:15)

Modalità d'Esame e Appelli

Le date degli appelli sono normalmente disponibili alla corrispondente pagina del corso di laurea.

L'esame consiste in una prova scritta, principalmente focalizzata sullo svolgimento di esercizi. Durante la prova scritta non è possibile consultare libri e/o appunti. Una prova orale è può essere sostenuta in modo opzionale (nel senso che viene concordata con il docente, ma può essere essenziale per confermare un risultato eccellente). La prova orale va sostenuta nello stesso appello dell'esame scritto. Dopo ogni prova scritta, sarà possibile prendere visione dei compiti e verrà proposta una correzione. I testi di alcuni esami degli anni accademici precedenti si possono trovare qui. Sono anche forniti alcuni esempi di esami risolti (i file con suffisso 'solved'). Si terrà una prova parziale facoltativa (nella settimana dedicata), che dà diritto ad un bonus fino a tre punti che si somma al voto della prova finale. Il bonus rimane valido per l'anno accademico.

Gli studenti degli anni accademici precedenti che hanno in piano l'insegnamento di Computabilità e Algoritmi da 12 CFU, supereranno l'esame sostenendo le prove dei due corsi Computabilità e Algoritmi Avanzati. Per Computabilità non potranno iscriversi alla lista. Sarà necessario inviarmi un messaggio per comunicarmi la volontà di partecipare ad un certo appello.

Riferimenti bibliografici

Si utilizzerà il seguente libro

• Nigel Cutland "Computability. An Introduction to Recursive Function Theory"
  Cambridge University Press