September 7, 2015
0.1 Time and place:
Thursday, 8:30–10:00, T 406/1, beginning October 8 2015.
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
(algorithmic) computability. 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 partial recursive
functions are investigated. In particular, this allows to derive negative results: certain
mathematical problems cannot be solved algorithmically even in principle. Some
considerations in computability theory also concern the old question whether or
not computers may completely replace humans (as mathematical problem
One natural sequel is the subject of abstract complexity, one of the topics in the
follow-up course Decidability- and Complexity Classes.
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.
- In order to support the claim that the class of partial recursive functions
coincides with that of algorithmically computable partial functions,
it is shown that it is closed under numerous operations, and that
many computable partial functions which occur in real life are indeed
partial recursive. Similar results are obtained for other basic notions of
- The first group of results are established which are really typical
for computability 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 method.
- 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.
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
Oral exam by agreement. Just consult me when you are ready.