RISC Logo
    News       Library       Links       Sitemap       Search  
line
 
 Computability Theory
 

Note

The lecture on December 10 has to be cancelled!

Preliminary meeting

October 2 2003 8:30am, K 123A. Some students asked to shift the lecture to a different time; this will be the main point to be discussed.

Time and place

It has been shifted to Wednesday 12:00-13:30, K 224B.

About the course

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.

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 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.

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.
    This page is maintained by Heinrich Rolletschek . Last updated on November 28, 2003