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]