ECTS
6 crédits
Composante
UFR Mathématiques
Volume horaire
9h
Période de l'année
Semestre 2
Description
- Calculabilité
- Fonctions primitives récursives et récursives, machines de Turing.
- Fonctions universelles et théorème s−m−ns−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
Heures d'enseignement
- Incomplétude et indécidabilitéCours Magistral4h
- Incomplétude et indécidabilité5h
Dernière mise à jour le 10 juillet 2023
