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