RISC JKU

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:

0.4 Literature:

Lecture notes will be handed out. Among textbooks we mention

0.5 Exam:

Oral exam by agreement. Just consult me when you are ready.