Computability Theory
Dr. Heinrich Rolletschek
October 1, 2009
Thursday, 8:30-10:00, HT 177F (K 177F), beginning October 1 2009
In contrast to other 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, in particular with limitations of computer programming. One typical kind
of result asserts that certain mathematical problems cannot be solved algorithmically even in principle. In
order to prove such facts, the classes of algorithmically computable functions and of
algorithmically decidable sets have to be defined formally, and their mathematical properties have to
be investigated. One natural sequel is the subject of abstract complexity, which is one of the topics of
the follow-up course Decidability- and Complexity Classes.
Chapters 1-6 deal with the following:
- Definition of the basic concepts of computability theory. For instance, the notion of recursive
function is regarded as being equivalent to the intuitive notion of algorithmically computable function,
but it is defined in a mathematically precise way.
- In order to support the claim that the class of recursive functions coincides with that of
algorithmically computable functions, it is shown that it is closed under numerous operations, and that
many computable functions which occur in real life are indeed recursive.
- 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 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 Company 2005.
Oral exam by agreement. Just consult me when you are ready.