Recursion Theory


Lecture in the winter term 2017/2018


Lecture Dates

Tue, 10:15 - 11:45am (5056)
Wed, 10:15 - 11:45am (5056)

Thu, 12:15 - 1:45pm (5054)



Recursion Theory is the theory of computable functions. It was originally developed by Gödel, Church, Kleene, Turing and Post, and results with very brief Arguments in extensive Insights. Here is just one example:

A saboteur tries to use an algorithm to change every C-program P in such a way, that the resulting program P' does something different than P. How can he achieve this? A main theorem of Recursion Theory states, that this is not possible, no matter what algorithmus he uses. The elegant terminology and conclusions obtained from Recursion Theory did serve as a model for many other disciplines, such as complexity theory.

We present an introduction to elementary terminology and facts of Recusion Theory, which build an important foundation for the discipline of computer schience.


This lecture can only be taken as a masters course.

Basic knowledge of "computability and complexity" theory is required for this course.



The course will be held in german.

Time and Place

Tuesday, 10:15am - 11:45am in 2356|056 (5056)
Wednesday, 10:15am - 11:45am in 2356|055 (5056)

This 3-hour course will be held as 4-hour course, but not every week. The exact dates will be announced in the first lecture and can be found in CampusOffice.


Martin Grohe







External Links