COMPUTABILITY
Academic Year 2022/2023 - Teacher: Domenico CANTONEExpected Learning Outcomes
Computability studies functions (and problems) which can be computed (solved) by way of a mechanical process, regardless of the quantity (though finite) of space/time resources.
The primary goal is therefore the formalization of the notion of algorithm, by means of effective models of computation. The primary model of computation adopted in the course is that of Unlimited Register Machines (URM). Other models will be quickly presented, such as that of Turing machines and that of general recursive functions. Such models (and all other models of computation that have been proposed over the years) are all equivalent, in the sense that a function can be computed in one of the models if and only if it can computed in the remaining ones. Thus, one can conjecture that, in particular, the URM model captures exactly the abstract concept of algorithm (Church-Turing thesis).
Much as a function is computable if its values can be calculated algorithmically, a problem or predicate is said to be decidable if it can be solved algorithmically.
By way of an effective enumeration of URMs (inspired by Gödel's numbering) and Cantor's diagonal method, examples of non-computable functions and undecidable predicates will be exhibited. The latter, in particular, include most problems of interest concerning the execution of computer programs.
The notion of decidability is generalized to that of partial decidability and we shall study various techniques (such as the technique of reduction. the Theorems of Rice and of Rice-Shapiro, and the Theorem s-m-n) to verify whether a given predicate is partially decidable or not.
Course Structure
Classroom-taught lessons
Should teaching be offered in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.
Required Prerequisites
Elements of discrete mathematics
Intuitive concept of algorithm
Elements of mathematical logic
Detailed Course Content
Computable functions: algorithms, effective procedures. URM model: Unlimited Register Machines. URM-computable functions. Decidable predicates and problems. Computability in other domains.
Generation of URM-computable functions: basic functions, composition or substitution, recursion, minimalisation.
Church-Turing's thesis: Other approaches to computability. Primitive recursive functions and general recursive functions. Turing machines. (Post and Markov systems.)
Enumeration of computable functions. Enumeration of URM-programs. The diagonal method. The s-m-n theorem
Universal programs: universal functions and universal programs (and applications). Effective operations on computable functions.
Decidability, undecidability and partial decidability: Undecidable problems in computability and in other areas of mathematics. Rice's theorem. Partial decidable problems.
Textbook Information
1) N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge - UK, 1986. [Main textbook]
2) M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994. [Recommended reading]
Course Planning
| Subjects | Text References | |
|---|---|---|
| 1 | Funzioni calcolabili: Algoritmi, procedure effettive. Modello URM: Unlimited Register Machines. Funzioni URM-calcolabili. Predicati e problemi decidibili. Calcolabilità su altri domini. | Cap. 1.1-1.5 di 1) e materiale didattico integrativo |
| 2 | Generazione di funzioni URM-calcolabili: Funzioni calcolabili di base. Composizione. Ricorsione. Minimalizzazione. | Cap. 2.1-2.5 di 1) e materiale didattico integrativo |
| 3 | Tesi di Church-Turing: Altri approcci alla computabilità. Funzioni ricorsive primitive e ricorsive generali. Macchine di Turing. | Cap. 3.1-3.4, 3.6 e 3.7 di 1) e materiale didattico integrativo |
| 4 | Sistemi di Post e di Markov | Cap. 3.5 di 1) |
| 5 | Enumerazione delle funzioni calcolabili: Enumerazione dei programmi URM. Metodo diagonale. Teorema s-m-n. | Cap. 4.1-4.4 di 1) e materiale didattico integrativo |
| 6 | Programmi universali: Funzioni e programmi universali (e applicazioni). Operazioni effettive su funzioni calcolabili. | Cap. 5.1-5.3 di 1) e materiale didattico integrativo |
| 7 | Problemi indecidibili in computabilità | Cap. 6.1 di 1) e materiale didattico integrativo |
| 8 | Problemi indecidibili in altre aree della matematica | Cap. 6.2-6.5 di 1) |
| 9 | Problemi semi-decidibili | Cap. 6.6 di 1) e materiale didattico integrativo |
| 10 | Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice-Shapiro | Cap. 7.1-7.2 di 1) e materiale didattico integrativo |
Learning Assessment
Learning Assessment Procedures
The final exam is essentially written. The verbalization may be preceded by a short discussion on the written assignment and, in doubtful cases, by a short oral test.
Verification of learning can also be carried out electronically, should the conditions require it.