Computability Theory
Dr. Heinrich Rolletschek
February 23, 2006
The time has been changed to Wednesday, 12:00-13:30 (beginning October 12), MZ 005B.
In contrast to other courses like Design and Analysis of Algorithms, where
specific algorithms are sought for specific problems, this course deals with the notion of (algorithmic)
computability itself, and 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 various operations, and that
many computable functions which occur in real life are indeed recursive.
- The diagonal method is introduced in order to establish the first results which are really typical for
computability theory; among them are the first undecidability results.
- Some alternative ways are discussed how the class of recursive functions could have been defined in the
first place; among the most well-known are µ-recursion and Turing machines.
- Further undecidability results are established by the method of reduction. This chapter contains
further 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.
Oral exam by agreement. Just consult me when you are ready.