Archive 2022
Program requirementsCC+examen
TeacherSylvy Anscombe
Weekly hours 4 h CM , 5 h TD
Years M1 Logos M1 mathématiques (MFA)

Contents

  • Calculabilité
    • Fonctions primitives récursives et récursives, machines de Turing.
    • Fonctions universelles et théorème $s-m-n$ ; problème de l'arrêt.
    • Ensembles récursifs et récursivement énumérables.
    • Théorème du point fixe.
    • Théorèmes de Rice et de Rice-Shapiro
  • Incomplétude
    • Arithmétique de Peano, axiomes.
    • Codage des formules.
    • Premier théorème d'incomplétude.
  • La hiérarchie arithmétique