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 (cenni), Classi di complessità temporale.La classe NP e NP-completezza.Il problema della soddisfacibilità proposizionale (SAT).Teorema di Cook.Catalogo di problemi NP-completi (a titolo indicativo): 3-SAT, n-SAT, VertexCover, CLIQUE, IndependentSet, HamiltonianPath, HamiltonianCircuit, LongestSimplePath, SetCover, HittingSet, SubgraphIsomorphism, TravelingSalesman, 3-DimensionalMatching, Partition, SubsetSum, Knapsack.La lista è da intendersi non esaustiva: alcuni problemi potranno essere trattati solo brevemente e altri, non menzionati, potranno essere introdotti durante il corso.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]