Calculabilités : Outils classiques
8 ECTS, semestre 2, 12 semaines
| Validation | CC+examen |
| Enseignant | Ludovic Patey et Julien Cervelle |
| Horaires hebdomadaires | 4 h CM |
| Années | Master Logique Mathématique et Fondements de l'Informatique M2 Logos |
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''.
La deuxième partie du cours traite de la complexité de Kolmogorov. On donnera les définitions et les propriétés élémentaires. Nous verrons comment on utilise la complexité algorithmique dans les preuves de complexité. Nous étudierons les objets aléatoires finis et infinis.
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