Scolarité M2 (sauf MIC, MIDS)
- Mme Chatoux
- bureau 5055
- 01 57 27 93 06
- Mme Prudlo
- bureau 5055
- 01 57 27 93 06
Calculabilités : Outils classiques
6 ECTS, semestre 2, 12 semaines
| Validation | CC+examen |
| Enseignant | Benoit Monin |
| Horaires hebdomadaires | 2 h CM |
| Années | Master Logique et Fondements de l'Informatique |
Syllabus
Ce cours est une continuation naturelle du cours "Calculabilité et incomplétude" du premier semestre. Les travaux de Godel, Church, Turing et d'autres, sur la définition formelle d'ensemble calculable, ont posés les bases sur lesquelles allait s'échafauder l'étude des degrés d'insolubilité : un important corpus de connaissances permettant de classer et comprendre l'univers des objets incalculables. Nous mèneront durant ce cours une étude détaillée de cet univers.
La calculabilité a aussi obtenu des succès majeurs en fournissant un cadre formel pour l'étude de certaines questions épistémologiques. Nous en verrons un exemple avec l'étude de l'aléatoire algorithmique. Nous verrons comment utiliser la calculabilité pour étudier avec une approche mathématique la question informelle de ce qu'est une suite de bits ``aléatoire''.
Bibliographie
- Computability theory, Barry Cooper, CRC Press, 2003
- Computability and Randomness, André Nies, OUP Oxford, 2009
- Algorithmic randomness and complexity, Downey/Hirschfeldt, Springer Science Business Media, 2010
- Classical recursion theory, Odifreddi, Elsevier, 1992