Incomplétude et indécidabilité
6 ECTS | Enseignant : Sylvy Anscombe | Validation : CC + examen
Horaires hebdomadaires : 4h CM, 5h TD | Mutualisé avec : M1 mathématiques (MFA)
Programme
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