UvA Logo

Recursion Theory
2003/2004; 1st Semester
Institute for Logic, Language & Computation
Universiteit van Amsterdam

Instructor: Dr Benedikt Löwe
Vakcode: MolRT6
Time: Thursday 3-5
Place: P.015A
First Lecture: September 11th, 2003
(Note that there will be no lecture on September 4th due to the traditional Introductory Boat Trip of the Master of Logic program. Also, there will be no lecture on October 23rd.)
Course language: English
Intended Audience: MoL students, Mathematics students in their fourth year
Prerequisites: This course assumes basic mathematical skills and some knowledge of basic logic.

This course will cover the basic notions of computability: Turing machines, recursivity and computer programs. The Equivalence Theorem will lead to Church's Thesis. Having a formalization of computability allows us now to investigate the boundaries of computation: what problems are not computationally solvable? This question will lead us to Turing's Halting Problem and the Decidability. We discuss several notions of recursion theoretic reducibility, their derived degree structures, and mathematical properties of these structures.

We shall mostly follow Part A of the textbook

Robert I. Soare, Recursively Enumerable Sets and Degres, A Study of Computable Functions and Computably Generated Sets, Springer-Verlag 1987.
In particular, we'll cover the following topics:

Topics covered so far:


Homework:

Extra Credit Assignments:

The idea of Extra Credit Assignments is to give you an opportunity to develop mathematical ideas of your own beyond the limited scope of a homework exercise. They are vaguely formulated and give you the chance to develop the proper definitions needed to prove the desired results.

The extra credit assignments are supposed to be an exercise in mathematical writing as well, so please try to hand them in in the style of textbook mathematics: definitions, lemmas, claims and theorems should be clearly marked as such, proofs should be marked by the word ``Proof'' and some marker that tells the reader that the proof is finished. LaTeXed solutions are strongly preferred for the extra credit assignments.

Extra Credit Assignments have no effect on the question whether you pass or fail the course. They can have a positive effect on your final grade, though.


Written Exam. The following is a possible written exam designed for 120 to 180 minutes. If you want, you can do it for training purposes: PostScript File.


Last update : February 5th, 2004