Recursion Theory

Advanced Lecture (Vertiefungsvorlesung), Summer Term 2015, 5 CP

People: Martin Zimmermann, Leander Tentrup
Lecture Room: E1 3, HS 003
Lectures: Thursdays, 10:15-12:00
Tutorials: Tuesdays, 09:00-10:00, E1 3, SR 015
Exams: End of Term: August 3rd, 2015 at 10am
End of Semester: October 12th, 2015 at 10am
Exam room: E1 3, HS 001

News

  • Tue, 06.10.: The second exam is rescheduled to October, 12th at 10am in lecture hall HS 001.
  • Sun, 04.10.: The second exam will be rescheduled. If you have registered for it, you should have received an email. If not, write Martin Zimmermann immediately.
  • Tue, 01.9.: We have 4 registrations for the end-of-semester exam. If you did not register because you cannot attend the exam, send an email to Leander Tentrup.
  • Wed, 05.8.: Updated results of the end-of-semester exam.
  • Tue, 04.8.: The results of the end-of-semester exam are online. The exam inspection is tomorrow, Wednesday, August 5th, 10:00 in Room 532 (building E1 3). In order to register for the end-of-term exam send an email to Leander Tentrup until September 1st.
  • Thu, 30.7.: The recap slides are available, please report errors by mail and watch this page for updates.
  • Wed, 29.7.: The evaluation of the lecture is available
  • Mon, 27.7.: The list of students that are admitted to the exam is available
  • Fri, 03.7.: Fixed typo in tenth problem set, Problem 3, part b: total recursive function g (instead of f)
  • Thu, 25.6.: The lecture next week (July 2nd) is moved to Friday, July 3rd, 12:00 (HS 003). The 10th problem set will be available on Tuesday, June 30th, after the tutorial.
  • Thu, 18.6.: The missing case of the equivalence proof for the two definitions of enumerability is available. Even better, the document also contains a simpler proof due to Yannick.
  • Thu, 11.6.: The sample solution for Exercise 6.1 is available (Username and password are given in the lecture)
  • Tue, 02.6.: The sixth problem set is available and due to June 9th
  • Fri, 29.5.: The explanation of the functions h2 and h3 in yesterday’s lecture was incorrect: we cannot use mod to set an entry of a sequence to 0, but have to use division. Here is a formal writeup.
  • Thu, 21.5.: The lecture on June 4th is moved to June 5th, 12:00 (HS 003), due to Corpus Christi.
  • Fri, 08.5.: The lecture on May, 14th is canceled due to Ascension Day. Therefore, also the tutorial on May, 19th is canceled.
  • Mon, 27.4.: The tutorial times changed to Tuesdays, 09:00-10:00.
  • Thu, 23.4.: Vote for an alternative tutorial slot until Monday, 4pm.
  • Fri, 10.4.: The tutorial times changed to Tuesdays, 12:00-13:00.
  • Thu, 26.2.: The first lecture is on Thursday, April 23rd, 2015.

Student Profile

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:

Show that there is an algorithm that given a natural number n terminates and answers whether the decimal expansion of pi contains n consecutive zeros.

Syllabus

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.

Topics

References

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.