Advanced Lecture (Vertiefungsvorlesung), Summer Term 2015, 5 CP
People: 
Martin Zimmermann, Leander Tentrup 
Lecture Room: 
E1 3, HS 003 
Lectures: 
Thursdays, 10:1512:00 
Tutorials: 
Tuesdays, 09:0010: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 endofsemester 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 endofsemester exam.
 Tue, 04.8.: The results of the endofsemester 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 endofterm 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 h_{2} and h_{3} 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:0010:00.
 Thu, 23.4.: Vote for an alternative tutorial slot until Monday, 4pm.
 Fri, 10.4.: The tutorial times changed to Tuesdays, 12:0013: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 noncomputable 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 noncomputable 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
 Goto programs
 Primitive recursive and recursive functions
 Computability
 Reducibility and Turing degrees
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 CampusBibliothek für Informatik und Mathematik.