Recursion Theory

 

Lecture in the winter term 2017/2018

 

Content

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.

Prerequisites

This lecture can only be taken as a masters course.

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

 

Organization

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.

Lecturer

Martin Grohe

 

Exercises

TBA

Exam

TBA