Computability : Classical tools

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.

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

• inscriptions
• calendrier
• accès
• Questions fréquentes

• Bâtiment Sophie Germain
  8 place Aurélie Nemours
  75013 Paris