COMPUTABILITY

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 which 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 to 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.

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.

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]