RISC Logo
    News       Library       Links       Sitemap       Search  
line
 
 Computability Theory
 

326.303-Computability Theory

Lecturer: Dr. Heinrich Rolletschek

Time and place: Thursday, 12:00-13: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:15-9: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 WL-program (or Turing machine or ...) which accomplishes to certain task.
  • Describe the function computed or language accepted by a given WL-program (or Turing machine etc.)
  • Give an example of a ...which ....
    This page is maintained by Heinrich Rolletschek . Last updated on February 22, 2002