Advanced Lecture (Vertiefungsvorlesung), Summer Term 2015, 5 CP
This course is aimed at mathematically interested students that want to study the foundations of computation. If you want to know the answer to the following puzzle, Recursion Theory is the right lecture for you:
Recursion Theory, also known as Computability Theory, is the study of the foundations of computation. Typical questions we will study are “Which functions can be computed?”, “How can the notion of algorithm be formalized and are those formalizations equally expressive?”, and “Are some non-computable problems harder than others?”.
We will answer these questions by studying a simple programming language and a mathematical model of computation, and by proving their equivalence, thereby answering the first two questions. Then, we delve into the theory of non-computable functions to answer the third question.
Recursion theory stands out as a beautiful theory with oftentimes simple, short, and surprising proofs (the algorithm solving the problem above has a single line of code) and historically forms the basis of complexity theory.
- Goto programs
- Primitive recursive and recursive functions
- Reducibility and Turing degrees
The course will be loosely based on the text book “Computability – An introduction to recursive functions” by Nigel Cutland, which is available at the Campus-Bibliothek für Informatik und Mathematik.