Théorie de la calculabilité - M1 2026-2027

Dans ce cours on se propose d’étudier, d’un point de vue formel, la notion de calcul effectif ou mécanique. Plus précisément, il s’agira de fournir une analyse logico-mathématique de notions qui concernent l’exécution d’une action de manière purement mécanique, c’est-à-dire sans faire appel à des formes d’intuition ou d’ingéniosité quelconques. Les instruments privilégiés pour poursuivre cette étude seront les fonctions récursives, suivant la tradition de K. Gödel et S.C. Kleene. Après avoir défini la classe de ces fonctions, on démontrera des théorèmes qui les concernent. D’une part, on établira des résultats positifs, comme la possibilité de ramener chacune de ces fonctions à une certaine forme normale, en donnant ainsi la possibilité d’avoir un modèle abstrait et universel de représentation des processus mécaniques de calcul. De l’autre, on établira des résultats négatifs – ou mieux limitatifs –, comme l’impossibilité de décider à l’avance si chaque processus de calcul mécanique s’arrêtera ou non.