Programma

 

• Introduzione alla teoria della ricorsività

Problemi della calcolabilità: le funzioni intuitivamente calcolabili, l'esistenza di funzioni non calcolabili. Linguaggi di programmazione: sintassi e semantica di un linguaggio RAM ridotto; sintassi e semantica del linguaggio While. Equivalenza dei due formalismi mediante la definizione di un interprete e di un compilatore. Aritmetizzazione dei programmi.
Funzioni ricorsive parziali. Funzioni primitive ricorsive e programmi loop. Tesi di Church. Sistemi di programmazione accettabili. Il teorema di ricorsione. Il teorema di isomorfismo. Problemi indecidibili. Il problema dell'arresto. Insiemi ricorsivi e ricorsivamente numerabili. Il teorema di Rice.
 

• Generalità sui linguaggi formali

Prime nozioni: monoidi liberi, linguaggi, grammatiche, derivazioni. Grammatiche di tipo 0, dipendenti da contesto, libere da contesto, regolari e le rispettive classi di linguaggi. Ricorsivit\à dei linguaggi dipendenti da contesto. Derivazione della parola vuota nelle grammatiche di tipo 1, 2, 3.
 

• Linguaggi regolari

Automi a stati finiti deterministici e non deterministici. Espressioni regolari. Teorema di Kleene. Lemma di iterazione per linguaggi regolari. Congruenze sintattiche e costruzione dell'automa minimo. Cenni agli automi a stati finiti 2-way.
 

• Linguaggi liberi da contesto

Alberi di derivazione. Semplificazioni nelle grammatiche libere da contesto. Forma normale di Chomsky. Algoritmo di riconoscimento di Cocke-Kasami-Young. Lemma di iterazione per i linguaggi liberi da contesto. Forma normale di Greibach. Automi a pila deterministici e non deterministici. Caratterizzazione dei linguaggi liberi da contesto mediante automi a pila. Grammatiche non ambigue e linguaggi inerentemente ambigui. Proprietà di chiusura dei linguaggi liberi da contesto. Problemi indecidibili definiti su linguaggi liberi da contesto.
 

• Complessità computazionale

Macchine di Turing deterministiche e non deterministiche. Risorse di calcolo: complessità in tempo e in spazio. Classi di complessità. Caratterizzazione dei linguaggi dipendenti da contesto mediante macchine di Turing lineari in spazio. Il teorema di Savitch.
Riduzione polinomiale. Le classi P e NP. Il teorema di Cook. Esempi di problemi NP-completi.
La riduzione in spazio logaritmico. Problemi completi per NL e P. Il teorema di Immerman-Szelepcsényi.

Testi di riferimento

• A.J. Kfoury, R.N. Moll, M.A. Arbib, A programming approach to computability , Springer-Verlag, 1982.
• J.E. Hopcroft, J.D. Ullman, Formal languages and their relations to automata, Addison-Wesley, 1969.
• J.E. Hopcroft, J.D. Ullman, Introduction to automata theory languages and computation, Addison-Wesley, 1979.
• Macchine di Turing e complessità computazionale (file dvi) (file ps). Appunti a cura del docente.