0.1 Time and place:

Thursday, 8:30–10:00, T 406/1, beginning October 10 2019.

0.2 About the course:

In contrast to courses like Design and Analysis of Algorithms, where specific algorithms are sought for specific problems, this course deals with the very notion of computability. What exactly do we mean, when we state that a problem can or cannot be solved algorithmically? And how can we prove rigorously that no algorithmic solution exists in certain cases? A famous result of this type (beyond the scope of this course) is the solution of Hilbert’s tenth problem: no algorithm can decide whether or not a given (polynomial) Diophantine equation has a solution (in the realm of integers). In order to show negative results of this kind, the notion of partial recursive function is introduced as a mathematically precise equivalent for the informal notion of algorithmically computable partial function, and mathematical properties of such functions are investigated.

One natural sequel is the subject of abstract complexity, one of the topics in the follow-up course Decidability- and Complexity Classes.

0.3 Contents:

Chapters 1–6 deal with the following issues:

• Partial recursive functions are defined formally, along with related notions like recursive function, recursive set and recursively enumerable set. For instance, a set A is recursively enumerable iff there exists a procedure for generating (enumerating) A.
• It is shown that numerous partial functions commonly encountered in mathematics are partial recursive, including all functions computed by computer programs in languages like ALGOL, C, etc. This of course provides considerable support for the claim that the class of partial recursive functions coincides with that of algorithmically computable partial functions. Also, it is shown that many mathematical operations, when applied to partial recursive functions, yield again partial recursive functions. Similar results are obtained for other basic notions of computability.
• The first group of results are established which are really typical for recursive function theory; they include the basic enumeration- and S-m-n-theorems, various characterizations of recursively enumerable sets, and the first undecidability result. The diagonal method is introduced as a basic proof technique.
• Some alternative ways are discussed how the class of partial recursive functions could have been defined in the first place; two of the most well-known ones use μ-recursion and Turing machines.
• Further undecidability results are established by the method of reduction. This chapter contains other typical results from recursive function theory, for instance, the famous fixed-point theorem.
• Elementary theory of reducibility. Intuitively, a problem P is reducible to a problem Q if any (hypothetical) algorithm for solving Q yields an algorithm for solving P. This intuitive concept can be made mathematically precise in various (nonequivalent) ways.

0.4 Literature:

Lecture notes will be handed out. Among textbooks we mention

• G. Tourlakis: Computability. Reston Publishing Company 1984.
• W. Brainerd, L. Landweber: Theory of Computation. Wiley 1974.
• M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company 2005.

0.5 Exam:

Oral exam by agreement.