Archive 2019
ValidationCC+examen
EnseignantBoban Velickovic
Horaires hebdomadaires 4 h CM , 6 h TD
Années M1 mathématiques (MFA)

Sommaire

  • 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