La théorie de la calculabilité s'intéresse essentiellement à la question suivante : au moyen d'un ordinateur, quelles fonctions peut-on calculer et quels problèmes peut-on résoudre ? Son développement est concomitant de l'apparition des principaux modèles de calcul (fonctions récursives, machines de Turing, lambda-calcul, ...) et est très étroitement lié à la logique mathématique (théorèmes d'incomplétude de Gödel). L'objectif de ce cours est de présenter des outils et résultats fondamentaux pour aborder ces questions.
Après des rappels sur la calculabilité (modèle des machines de Turing, langages semi-décidables et décidables, réductions et théorème de Rice), le cours développera librement des éléments relatifs aux thèmes suivants, qui s'intersectent sous de multiples aspects : thèse de Church-Turing, construction d'une machine de Turing universelle, théorèmes du point fixe de Kleene et auto-référence, théorèmes d'incomplétude de Gödel, complexité de Kolmogorov, concours du castor affairé, automates cellulaires, indécidabilité de la logique du premier ordre, problème de correspondance de Post, degrés Turing et calculabilité relative...
Bibliographie :
-
M. Sipser, Introduction to the Theory of Computation, Cengage Learning, 2012.
-
R. Cori, D. Lascar, Logique mathématique II : fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles, Axiomes, Masson, 1993.
-
J.-L. Krivine, Lambda-calcul, types et modèles, études et recherches en informatique, Masson, 1990.
