326.303Computability Theory Lecturer: Dr. Heinrich Rolletschek Time and place: Thursday, 12:0013:30, BA 9908. Contents: Various courses deal with specific algorithms for specific problems like sorting, polyomial
factorization etc. In computability theory the very concept of algorithm is investigated, and the class of
algorithmically computable functions is defined in a mathematically precise fashion, as are the related classes
of decidable and of recursively enumerable sets. Thus the course provides a rigorous mathematical basis for
programming, similarly as logic provides a basis for mathematical reasoning. Such a systematic approach is
necessary in particular to prove negative results: certain problems can not be solved algorithmically, even in
principle. The main topics are:
 Definition of the basic concepts of computability
 Proof that many common functions are (partial) recursive
 First undecidability results; diagonalization
 Various alternative models of computability
 More undecidability results, enumerations and the recursion theorem
 Basic theory of reducibility relations
Literature: Lecture notes will be given out. Final exam: Friday 1.3.2002, 8:159:45, K 012 (Keplergebäude) You are not allowed to use written notes. Of course you have to know defintions, theorems etc., but no proofs
of theorems will be asked, and no technical details which have nothing to do with the general understanding of
the material and which it would be pointless to learn by heart (for instance, the precise definition of the
coding scheme for tuples of numbers). The following types of questions should be expected:
 General knowledge questions.
 Justify the following assertion: .... (In such cases an answer can be given based on an understanding
of the material.)
 Construct a WLprogram (or Turing machine or ...) which accomplishes to certain task.
 Describe the function computed or language accepted by a given WLprogram (or Turing machine etc.)
 Give an example of a ...which ....
