Calcolabilità e complessità computazionale

Introduzione alla calcolabilità: le funzioni intuitivamente calcolabili, esistenza di funzioni non calcolabili, la funzione coppia e le sue estensioni. Sintassi e semantica del linguaggio RAM ridotto. Sintassi e semantica del linguaggio While. Esempio di funzione compilatore e di funzione interprete. Equivalenza computazionale tra linguaggio RAM e linguaggio While. Aritmetizzazione dei programmi RAM. Funzioni ricorsive parziali. Tesi di Church.
Sistemi di programmazione accettabili. Il teorema di ricorsione e il teorema di isomorfismo. I problemi indecidibili. Problemi particolari: arresto, totalità, equivalenza. Insiemi ricorsivi e ricorsivamente numerabili. Caratterizzazioni principali degli insiemi ricorsivamente numerabili. Riducibilità tra insiemi e insiemi completi. Insiemi che rispettano le funzioni. Il teorema di Rice.
Linguaggi e grammatiche formali. Gerarchia di Chomsky: linguaggi regolari, liberi da contesto, dipendenti da contesto, di tipo 0. Automi a stati finiti deterministici, non deterministici e loro proprietà di simulazione. Linguaggi regolari: lemma di iterazione e proprietà di chiusura rispetto alle operazioni booleane.
Macchine di Turing. Macchine deterministiche e non deterministiche. Proprietà di simulazione tra modelli. Classi di complessità in tempo. Classi P e NP. Riducibilità in tempo polinomiale e suoi esempi notevoli. I problemi NP-completi. Il teorema di Cook. Introduzione alla complessità in spazio: le classi L, NL, Pspace. Complessità del problema della raggiungibilità. Il teorema di Savitch.