Prerequisites
A first course in mathematical logic, comparable to the material in the book J. van Oosten and I. Moerdijk, Sets, Models, and Proofs.
In particular, acquaintance with propositional logic, first order predicate logic and basic set theory is required.
Aim of the course
The goal of the course is to make the student acquainted with the topics mentioned below and to prepare the student for more advanced topics in computability theory
and descriptive set theory.
- recursive functions
- arithmetization
- the equivalence of various definitions of the class of computable functions
- reducibilities
- the arithmetical hierarchy
- relative computation and Turing reductions
- the recursion theorem
- diagonalization
- applications
- Kolmogorov complexity
- algorithmic randomness
- miscellaneous advanced topics
Rules about Homework/Exam
There will be a written exam at the end.
There will be no homework assignments that count toward the final grade.
The retake will be either a written or an oral exam, depending on the number of students.
Lecture notes/Literature
S. A. Terwijn, Syllabus Computability Theory,
available from the web page of the lecturer.
Lecturers
Sebastiaan Terwijn
- Docent: Komi Golov
- Docent: Sebastiaan Terwijn