Modèles de calculs –­machines de Turing

L3 Informatique, U. Grenoble Alpes

Pour l’autre partie du cours Modèles de calculs, qui traite de lambda-calcul, visiter la page dédiée.

Cours

Le plan indiqué est prévisionnel et susceptible de modifications. Les diapositives manquantes seront mises en lignes rapidement. Celles de l’an dernier sont disponibles en attendant.

1. Introduction : présentation du cours ; machines de Turing
2. Variantes des machines de Turing : taille de l'alphabet, nombre de ruban, forme du ruban, non-déterminisme
3. Thèse de Church-Turing : reconnaître, décider, calculer ; machine RAM et langage while ; tous les modèles (raisonnables) sont équivalents
4. Incalculabilité : incalculabilité par dénombrement ; machine universelle ; problème de l'arrêt
5. Incalculabilité (suite) : théorème de Rice, langages non (co-)reconnaissables
6. Autres problèmes incalculables : pavage du plan, problème de correspondance de Post
7. Fonctions primitives récursives : langage loop et fonction d'Ackermann-Péter
8. Bilan du cours

• 2025 +-
  1. Introduction : présentation du cours ; machines de Turing
  2. Variantes des machines de Turing : taille de l'alphabet, nombre de ruban, forme du ruban, non-déterminisme
  3. Thèse de Church-Turing : reconnaître, décider, calculer ; machine RAM et langage while ; tous les modèles (raisonnables) sont équivalents
  4. Incalculabilité : incalculabilité par dénombrement ; machine universelle ; problème de l'arrêt
  5. Incalculabilité (suite) : théorème de Rice, langages non (co-)reconnaissables
  6. Autres problèmes incalculables : pavage du plan, problème de correspondance de Post
  7. Fonctions primitives récursives : langage loop et fonction d'Ackermann-Péter
  8. Bilan du cours
• 2024 +-
  1. Introduction
  2. Variantes des machines de Turing
  3. Thèse de Church-Turing
  4. Incalculabilité – diagonalisation
  5. Incalculabilité explicite
  6. Autres problèmes incalculables
  7. Fonctions primitives récursives
  8. Bilan du cours

Sujets de TD et annales

• TD : livret de TD
• Quick : évaluation continue
• Examen : examen final

• 2025 +-
  • TD : livret de TD
  • Quick : évaluation continue
  • Quick-Correction : éléments de correction
  • Examen : examen final
• 2024 +-
  • TD1 : machines de Turing et variantes
  • TD2 : thèse de Church-Turing
  • TD3 : incalculabilité
  • Quick : évaluation continue
  • Quick-Correction : éléments de correction
  • Examen : examen final

Code et exemples

• Exemples de machines de Turing présentées en cours, pour visualisation sur le site turingmachine.io :

  • Cours 1
  • Cours 2
  • Cours 3 (à venir)
  • Cours 4 (à venir)

• Implantation en Python des transformations présentées en cours : classes TuringMachine, RAM et While (à venir)

  • Exemples du cours 1
  • Exemples du cours 2
  • Exemples du cours 3 (à venir)
  • Exemples du cours 4 (à venir)

Quelques lectures, vidéos et liens intéressants

• Vidéo d’introduction du cours : le problème de la décision (Arte)

Machines de Turing

• Vidéo : une machine de Turing en Lego (CNRS)
• Article Interstices : Comment fonctionne une machine de Turing ?
• Applis web : Simulateur de machine de Turing (logiciel libre) ; Simulateur de machine de Turing à plusieurs rubans

Thèse de Church-Turing

• Vidéos sur le jeu de la vie : sur Arte et Science Étonnante
• Articles Interstices :
  • Le calcul, une notion difficile à attraper
  • Alan Turing : du concept à la machine
  • La riche zoologie des automates cellulaires
  • Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing
• Articles dans Pour la Science (consultables à la BU) :
  • Jean-Paul Delahaye, « Une théorie rêvée du calcul », Pour la Science n°527, février 2014.
  • Jean-Paul Delahaye, « Programmer avec… des origamis », Pour la Science n°566, novembre 2024.

Indécidabilité

• Vidéos sur l’infini : sur Arte et Science Étonnante
• Article Interstices : Alan Turing : du calculable à l’indécidable
• Sean Bailly, « Les indécidables trajectoires d’un fluide », Pour la science n°526, juillet 2021.
• Sur le busy beaver (ou caster affairé) :
  • With Fifth Busy Beaver, Researchers Approach Computation’s Limits, Quantamagazine, juillet 2024 (en anglais)
  • Le défi du « castor », une conjecture mathématique vieille de plus de 30 ans, résolu par une équipe constituée en partie d’« amateurs », dans Le Monde, juillet 2024. Accessible via Europresse (chercher le titre dans la barre de recherche).

Bibliographie indicative

Ces références sont présentes pour celles et ceux qui le souhaitent, mais il n’y a aucune obligation à les consulter. Elles peuvent soit vous permettre d’avoir une autre présentation des sujets traités en cours, soit d’aller plus loin car elles abordent des sujets non traités.

• Références principales, en anglais (qui couvrent bien plus que le cours !) :

  • B. Barak, Introduction to theoretical computer science, 2023 (work in progress). Livre accessible en ligne en format html ou pdf, à conseiller très fortement ! Inutile d’aller au delà du chapitre 10 pour ce cours.

  • R. Sedgewick and K. Wayne, Computer science: an interdisciplinary approach. Addison-Wesley, 2017. Livre très abordable, très bien fait !

  • M. Sipser, Introduction to the theory of computation, 3. ed. Andover: Cengage Learning, 2013. Encore un livre assez abordable, mais bien plus formel.

• Livres en français, accessibles à la bibliothèque universitaire :

  • P. Wolper, Introduction à la calculabilité : cours et exercices corrigés, 3è éd., Dunod, 2006.

  • O. Ridoux, G. Lesventes, Calculateurs, calculs, calculabilité, Dunod, 2008. Calculabilité sans machine de Turing.

  • O. Carton, Langages formels, calculabilité et complexité, Vuibert, 2008.

  • J.-M. Autebert, Calculabilité et décidabilité : une introduction, Masson, 1992.

• Notes de cours en français disponible en ligne :

  • E. Asarin, Calculabilité, 2003. Super notes de cours sur la calculabilité (par un ancien enseignant de Grenoble) ! Tout y est, de manière concise. Très chaudement recommandé !

  • K. Perrot, Calculabilité, 2022-2023. Un ensemble de notes de cours, sujets de TD, examens, etc. d’un collègue marseillais.

Dernière modification : 10 janvier 2026