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.

1. Introduction : présentation du cours ; machines de Turing

   • Vidéo Arte : le problème de la décision
   • Vidéo CNRS : une machine de Turing en Lego
   • Appli web : Simulateur de machine de Turing (logiciel libre)
   • Article Interstices : Comment fonctionne une machine de Turing ?

2. Variantes des machines de Turing : taille de l’alphabet, nombre de ruban, forme du ruban, non-déterminisme

   • Appli web : Simulateur de machine de Turing à plusieurs rubans

3. Thèse de Church-Turing : reconnaître, décider, calculer ; machine RAM et mini-langage de programmation ; tous les modèles (raisonnables) sont équivalents

   • 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

4. Incalculabilité – diagonalisation : dénombrabilité ; incalculabilité par dénombrement

   • Vidéos sur l’infini : sur Arte et Science Étonnante
   • Vidéos sur le théorème de Gödel : sur Arte et Science Étonnante
   • Article Interstices : Alan Turing : du calculable à l’indécidable

5. Incalculabilité explicite : problème de l’arrêt et variantes, théorème de Rice, etc.

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

Sujets de TD

• Feuille n°1 : machines de Turing et variantes
• Feuille n°2 : thèse de Church-Turing
• Feuille n°3 : incalculabilité

Sujets d’examens

• Évaluation continue et éléments de correction

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 : 25 mars 2024