Funzioni calcolabili: Algoritmi, procedure effettive. Modello URM: Unlimited Register Machines. Funzioni URM-calcolabili. Predicati e problemi decidibili. Calcolabilità su altri domini.Generazione di funzioni URM-calcolabili: Funzioni calcolabili di base. Composizione. Ricorsione. Minimalizzazione.Tesi di Church-Turing: Altri approcci alla computabilità. Funzioni ricorsive primitive e ricorsive generali. Macchine di Turing. (Sistemi di Post e di Markov)Enumerazione delle funzioni calcolabili: Enumerazione dei programmi URM. Metodo diagonale. Teorema s-m-n.Programmi universali: Funzioni e programmi universali (e applicazioni). Operazioni effettive su funzioni calcolabili.Decidibilità, indecidibilità e semi-decidibilità: Problemi indecidibili in computabilità e in altre aree della matematica. Teorema di Rice. Problemi semi-decidibili.Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice-Shapiro.

1) N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge - UK, 1986. [Testo principale]2) M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994. [Lettura consigliata]

Notazioni asintotiche,Funzioni numeriche (Turing) computabili.Classi di complessità temporaleLa classe NP eNP-completezzaIl problema della soddisfacibilità proposizionale (SAT).Teorema di CookCatalogo di problemi NP-completi (3-SAT, n-SAT, VertexCover, CLIQUE, IndependentSet,HamiltonianPath, HamiltonianCircuit, LongestSimplePath, SetCover, HittingSet,SubgraphIsomorphism, TravelingSalesman, 3-DimensionalMatching, Partition, SubsetSum, Knapsack)Complessità spaziale delle macchine di Turing

1) N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge - UK, 1986. [Testo principale]2) M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994. [Lettura consigliata]