Scolarité M2 (sauf MIC, MIDS)
- Mme Chatoux
- bureau 5055
- 01 57 27 93 06
- Mme Prudlo
- bureau 5055
- 01 57 27 93 06
Incomplétude et indécidabilité
6 ECTS, semestre 2, 6 semaines
| Validation | CC+examen |
| Enseignant | Sedki Boughattas |
| 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