Computability Theory
Dr. Heinrich Rolletschek
September 9, 2013
0.1 Time and place:
Thursday, 8:30–10:00, T 642, beginning October 3 2013
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. What precisely does it mean to say that certain
mathematical problems cannot be solved algorithmically even in principle? Negative
results of this kind are typical for computability theory. As it turns out, various
attempts to formalize the notion of computability all give rise to the same notion of
partial recursive function, and there are good arguments to regard it as a precise
mathematical equivalent for the informal notion of algorithmically computable
partial function. Certain considerations in computability theory also cocern the old
question whether or not computers may completely replace humans (as mathematical
problem solvers).
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:
- 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.
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. Just consult me when you are ready.