Computability theory and applications

Speaker: Ludovic Patey, CR CNRS at Institut Camille Jordan

The aim of this course is to give a solid background on computability theory, by covering the basic notions (Church-Turing thesis, Turing degrees, Pi^0_1 classes, the arithmetic hierarchy, hyperimmunity, finite extension method and priority constructions) but also more advanced topics such as a gentle introduction of computable forcing, reverse mathematics and algorithmic randomness.

Prerequisites: No specific prerequisite is necessary, except some mathematical maturity. It is helpful to have some basic notions of set theory, in particular Cantor's diagonal argument, or some basic knowledge of first order logic.

Bibliography: 
Cooper, Computability theory
Soare, Turing computability : theory and applications