1) 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 and first order predicate logic and basic set theory is required.
2) Aim of the course
Computability theory is a subfield of mathematical logic, in which mathematical problems are classified according to how computable or noncomputable they are. The field emerged in the 1930s from the various definitions of the class of computable functions in the work of Gödel, Turing, Church and others. The question of what is computable is closely related to the question about what is provable in mathematics.
Although Gödel's famous incompleteness theorem is a result about about provability, computability theory offers the right setting do discuss its proof, as well as that of related results such as the unsolvability of the Entscheidungsproblem. The arithmetical hierarchy and Turing reductions allow us to classify how noncomputable given sets and functions are. The basic notions of computability theory offer a fine-grained view on mathematical problems, with applications in computer science, proof theory, constructive mathematics, and algorithmic randomness.
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 degrees
the recursion theorem
diagonalization
applications
Kolmogorov complexity
algorithmic randomness
miscellaneous advanced topics
At the end of the course the student should be able to
- classify problems in the arithmetical hierarchy
- build reductions and give completeness proofs
- perform diagonalization constructions
- give applications of the recursion theorem
- apply the basic notions of computability to other fields
- prove results in Kolmogorov complexity and algorithmic randomness
3) 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.
4) Lecture notes/Literature
S. A. Terwijn, Syllabus Computability Theory,
available from the web page of the lecturer.
5) Lecturers
Sebastiaan Terwijn
- Docent: Sebastiaan Terwijn