Archive 2022
Program requirementsCC+examen
TeacherLudovic Patey and Julien Cervelle
Weekly hours 4 h CM
Years Master Logique Mathématique et Fondements de l'Informatique M2 Logos

Syllabus

This course is a direct continuation of the first semester course "Computability and incompleteness". The work of Godel, Church, Turing and others on the formal definition of computable sets, started a new field of research : The degrees of unsolvability, a very rich and fruitful theory which provides classification and understanding about the universe of non-computable objects. We will present during this course a detailed study of this universe.

Computability has also obtained major successes by providing a formal framework to study some epistemological questions. We will see an example of that with the study of algorithmic randomness. We will see how to use computability to study with a mathematical approach the informal question of what is a random sequence of bits.

The second part of the course deals with Kolmogorov complexity. We will give the definitions and the elementary properties. We will see how algorithmic complexity is used in proofs of complexity. We will also study finite and infinite random objects.

Bibliography

  • Computability theory, Barry Cooper, CRC Press, 2003
  • Computability and Randomness, André Nies, OUP Oxford, 2009
  • Algorithmic randomness and complexity, Downey/Hirschfeldt, Springer Science Business Media, 2010
  • Classical recursion theory, Odifreddi, Elsevier, 1992