[Fall 2020]

Prerequisites

Basic knowledge of mathematical logic
(that is, familiarity with predicate logic, models, formal proofs, Gödel's completeness theorem, basic set theory, cardinalities) as well as the mathematical maturity required for a master's course in mathematics.

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

Lecturers
Sebastiaan Terwijn