# Recursion Theory

Summer Term 2021

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

This 3-hour course will be held as 4-hour course, but not every week. The exact dates will be announced soon.

Lecturer

Exercises

TBA

Exam

TBA