Calculabilité et incomplétude

Code APOGÉE : MA4BY030 | 12 ECTS | Enseignant : Arnaud Durand | Validation : examen
Horaires hebdomadaires : 4h CM, 2h TD | Mutualisé avec : M2 LMFI

Programme

Calculabilité

• Fonctions récursives et fonctions calculables par machine
• Caractérisation logique des fonctions calculables
• Théorème s-m-n et théorèmes de point fixe
• Notions de réduction et problèmes indécidables

Introduction à la complexité

• Classes en temps et espace
• Théorèmes de hiérarchie
• Réductions, complétude
• Circuits booléens
• Introduction à la complexité algébrique

Arithmétique formelle

• Axiomes de Peano et sous-systèmes faibles
• Arithmétisation de la logique
• Théorèmes d’indécidabilité
• Les théorèmes d’incomplétude de Gödel

Bibliographie

• Barwise, J. (Ed.) (1977-1999). Handbook of Mathematical Logic. Amsterdam : North-Holland.
• Cori, R. & Lascar, D. (2003). Logique mathématique : cours et exercices (2 tomes). Paris : Dunod.
• Lassaigne, R. & de Rougemont, M. (1996). Logique et Complexité. Paris : Hermès.
• Machtey, M. & Young, P. (1978). An introduction to the General Theory of Algorithms. Amsterdam : North Holland.
• Schoenfield, J. R. (1967, 2001). Mathematical Logic. Reading : Addison-Wesley. Association for Symbolic Logic.
• Smullyan, R. (1993). Les Théorèmes d’Incomplétude de Gödel. Paris : Masson.
• Goldreich, O. (2008). Computational Complexity : A Conceptual Perspective. Cambridge : Cambridge University Press.
• Jones, N. D. (1997). Computability and Complexity : From a Programming Perspective. Cambridge : MIT Press.