Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°79 - mars 2022 > La machine de Turing (1/2)

La machine de Turing (1/2)
Moteur de recherche
Mis en ligne le 12 janvier 2022, par Patrice Debrabant

La machine de Turing est une machine élémentaire. On considère souvent que c’est le modèle théorique d’un ordinateur (ce qui est partiellement vrai).
Bien qu’élémentaire, cette machine est traversée par les problématiques fondamentales de l’informatique, et ces problématiques sont souvent exprimées en termes de machines de Turing.
Dans ce premier article, Patrice Debrabant présente cette machine et l’implémente.

Un second article sur la machine de Turing traitera de complexité (dans le prochain numéro, en mai 2022).

Voir aussi

Alan Turing (1912 - 1954) est un mathématicien anglais dont les travaux ont fondé l’informatique théorique et inspiré le développement des ordinateurs. Il est célèbre pour avoir décrypté la machine Enigma, dispositif de codage redoutable qu’utilisaient les armées allemandes pour leurs communications lors de la seconde guerre mondiale.

Machine Enigma
Machine Bombe (reconstitution)

Pour relever ce défi de décryptage, Turing utilisa une machine appelé "La Bombe" [1]. Ce n’est pas à cette machine que l’on va s’intéresser dans cet article.

La machine de Turing est une machine abstraite. On peut la construire (ou la simuler, comme on le fera dans cet article). Mais l’important n’est pas tant de la construire (elle ne produit que des banalités) que de la comprendre (son fonctionnement est instructif et fondamental).

Pour bien comprendre ce qu’est une machine de Turing, il convient de revenir sur le contexte dans lequel elle est apparue en 1936.
On peut considérer que la préhistoire de cette machine commence en 1900 avec le grand mathématicien David HILBERT. A cette époque, il règne un certain optimisme dans les sciences :

  • en physique, la mécanique newtonienne modélise le monde de façon claire et conforme à l’intuition ;
  • en mathématiques, l’idée semble s’imposer que toutes les propriétés peuvent découler d’une axiomatisation bien choisie et qu’elles peuvent être démontrées dans le cadre de cette axiomatisation.

En 1900, à l’occasion du Congrès international des mathématiciens de Paris, Hilbert énonce une liste de 23 problèmes fondamentaux.
Le 10e de ces problèmes porte sur les équations diophantiennes :

Décidabilité de la résolubilité d’une équation diophantienne
Etant donnée une équation diophantienne à un nombre arbitraire d’inconnues et dont les coefficients sont des nombres entiers, donner un procédé qui au moyen d’un nombre fini d’opérations permet de décider si l’équation possède une solution entière.
Les équations diophantiennes dont il s’agit sont les équations de la forme
$P(x, y, z, . . . ) = 0$, où $P$ est un polynôme à coefficients entiers en des inconnues $x, y, z$, . . . [2]

En 1928, HILBERT généralisa deux de ses problèmes de 1900 et posa l’Entscheidungsproblem (problème de décision).
Il s’agissait de démontrer :

  • que toute assertion mathématique vraie peut être démontrée (complétude des mathématiques) ;
  • que seules des assertions mathématiques vraies peuvent être démontrées (consistance des mathématiques) ;
  • le problème de décision : les mathématiques sont décidables, autrement dit il existe un algorithme permettant de décider de la vérité (ou non) de toute assertion mathématique.

Il y avait là une vision radicale de l’édifice mathématique qui semblait naturelle. L’ambition conquérante d’HILBERT s’appuyait sur un socle qui pouvait sembler inébranlable. Mais cet univers de la certitude allait bientôt se fissurer de toutes parts.

À la surprise de HILBERT, Kurt GÖDEL démontra en 1930 que les deux premiers problèmes ont une réponse négative.

Le troisième problème quant à lui nécessitait la définition mathématique du mot « algorithme ».
Ce concept peut être défini simplement et précisément en termes de machines de Turing [3], et TURING démontra en 1936 (dans le même article qui présentait ses machines) que la réponse au problème de décision est négative [4] : il n’existe pas d’algorithme permettant de décider de la vérité (ou non) de toute assertion mathématique pour l’arithmétique (par exemple l’arithmétique de Peano ou toute théorie plus forte).

La machine de Turing : une machine élémentaire traversée par les problématiques essentielles de la science informatique

  1. Qu’est-ce qu’une machine de Turing ?
  2. Machine de Turing et calculabilité
  3. Machine de Turing et complexité

1) Qu’est-ce qu’une machine de Turing ?

L’idée de base est de modéliser de façon la plus simple possible un dispositif mécanique permettant de réaliser les opérations élémentaires effectuées par une personne équipée d’un crayon et d’une gomme appliquant un algorithme.

Le support d’écriture est un ruban linéaire bi-infini.
Sur ce ruban initialement vierge, on peut écrire et effacer des symboles d’un alphabet fini.
La machine possède plusieurs états (en nombre fini). A chaque étape, elle est dans un état particulier et cet état conditionne le comportement de la machine à cette étape :

  • la machine lit le symbole écrit sur le ruban au niveau de sa tête de lecture ;
  • la machine efface ce symbole et écrit un nouveau symbole ;
  • la tête de lecture se déplace d’une case à droite ou à gauche.

Si la machine atteint un état d’arrêt, elle s’arrête.

En termes mathématiques, une machine de Turing est constituée :

  • d’un nombre fini d’états $Q = { q_1,.. q_n}$
    $q_1$ est l’état initial
    $q_{accepter}$ est l’état d’acceptation.
    $q_{\text{rejeter}}$ est l’état de rejet, avec $q_{\text{rejeter}} \neq q_{accepter}$.
  • d’un alphabet d’entrée $\Sigma$ fini qui ne contient pas le symbole blanc.
    L’alphabet du ruban $\Gamma$ est $\Sigma \cup \{blanc\}$
  • d’un (ou plusieurs) ruban(s) sur lequel la machine peut lire et écrire des symboles de $\Sigma$ ;
  • d’une fonction de transition $\Delta : Q \times \Gamma \mapsto Q \times \Gamma \times \{G,D\}$. (G signifie que la tête de lecture se déplace d’une case vers la gauche, D signifie qu’elle se déplace d’une case vers la droite.)

Exemple 1

Trouver une séquence et en remplacer les 0 par des 1.
Une séquence de 0 et de 1 est écrite sur le ruban et la tête est à gauche de cette séquence.

On construit le diagramme de la machine de la façon suivante :
Les états sont écrits sous la forme q1, q2, etc. qF représente l’état final. [5]

Les déplacements à gauche et à droite sont représentés par les lettres L et R (Left et Right).
Les triplets indiqués représentent (lecture ; écriture ; déplacement) et la flèche indique le prochain état.

Et voila le résultat :

On va modéliser cette machine de Turing avec Scratch.
Pour cet exemple, on peut se contenter d’un ruban infini dans un seul sens (la tête de lecture restant toujours à droite de la position initiale). Ce ruban sera modélisé par une liste. Dans le cas général, on pourrait modéliser le ruban par 2 listes articulées ou plus simplement, comme on le fera plus tard, en gardant une seule liste mais en partant d’une position élevée (100 par exemple).

On modélise chaque état par un lutin et on exploite la fonctionnalité d’envoi de message.

Voici par exemple le script de q2.

Un clic sur le drapeau vert initialise le ruban.
Un clic sur la barre espace lance la machine de Turing.

lien vers le fichier Scratch en ligne

Remarque : on peut se demander si cette façon de programmer est une « bonne façon de programmer ».
Marie Duflot-Kremer, France Gall de la pédagogie [6], propose une version débranchée de la machine de Turing. Est-ce préférable ?...

Pourquoi la machine de Turing est-elle fondamentale ?

La machine de Turing est une machine élémentaire. On peut difficilement faire plus simple.
Pourtant, on peut démontrer que :

  • toute fonction qui peut être calculée par une machine "classique" plus sophistiquée (par exemple un ordinateur) peut être calculée par une machine de Turing ; ($\rightarrow$ calculabilité)
  • (dans un domaine que l’on précisera et en un sens que l’on précisera) une machine classique plus sophistiquée ne calcule pas réellement plus vite qu’une machine de Turing. (!) ($\rightarrow$ complexité)

2) Calculabilité

Tout ce qui peut « se calculer » (par une série d’opération et de manipulations simples, autrement dit par un « algorithme ») peut être calculé par une machine de Turing.
La machine de Turing peut-être très lente en pratique. Mais elle peut le faire.
C’est ce que l’on appelle la « thèse de Church » : rien de « calculable » n’échappe à la portée des machines de Turing. Il ne s’agit pas d’une propriété, mais plutôt d’une "définition réfléchie" de ce qui est calculable et de ce qui ne l’est pas.

Exemples (classiques) de machines de Turing

Addition en unaire

Écrire un nombre en unaire revient à écrire autant de 1 que la valeur du nombre.
Exemple : 5 s’écrit en unaire 11111.

On veut ici additionner deux nombres représentés en unaire (dans l’exemple présent 2 et 3), et séparés par un espace blanc.

Pour cela la tête de lecture va parcourir le premier nombre, arrivée sur le blanc, elle va écrire un 1, puis elle va parcourir le deuxième nombre. Arrivée au blanc elle va reculer d’une case et va terminer en mettant à blanc le 1 le plus à droite.

Lien vers le fichier Scratch en ligne

Remarque : comme précédemment, on peut se contenter d’un ruban infini dans un seul sens (la tête de lecture restant toujours à droite de la position initiale).


Soustraction en unaire

Faire une soustraction en unaire avec x < y : deux nombres X et Y sont écrits en unaire et séparés par un blanc, X est inférieur à Y et la tête est sous le chiffre de gauche deX.
On pourra, successivement, remplacer un 1 de X par un 0 et supprimer un 1 de Y.

Le départ

Le résultat

Lien vers le fichier Scratch en ligne

Écrire un 1 si une séquence contient un nombre pair de 1

Lien vers le fichier Scratch en ligne

Tester si un mot est un palindrome

La réponse est le dernier bit du ruban dans l’état final :
1 si le mot est un palindrome
0 sinon.

Lien vers le fichier Scratch en ligne

Ajouter 1 en base 2

Lien vers le fichier Scratch en ligne

On peut alors s’intéresser au problème de décision : est-ce qu’il existe une machine de Turing permettant de décider de la vérité (ou non) de toute assertion mathématique ?
Autrement dit, existe-t-il une machine de Turing à laquelle on peut soumettre une assertion mathématique et qui, pour toute assertion, s’arrête au bout d’un temps fini dans un état d’acceptation ou dans un état de refus ?
La réponse est non, et Turing l’a démontré par l’absurde.

Avant de présenter cette démonstration, basée sur un « argument diagonal », il nous faut faire un petit détour. L’idée est de faire appel à une machine de Turing qui s’applique à elle-même. Mais encore faut-il donner un sens précis à cette idée.
Une machine de Turing est un dispositif simple, avec un nombre fini d’options. On peut clairement « coder » une machine de Turing, autrement dit associer à toute machine de Turing un codage distinct, parfaitement déterminé.
Par exemple, on peut coder le nombre d’états, puis l’alphabet, puis la fonction de transition,...
En voyant le code, on sait alors de quelle machine de Turing il s’agit. [7]

Revenons à notre question : existe-t-il une machine de Turing à laquelle on peut soumettre une assertion mathématique et qui, pour toute assertion, s’arrête au bout d’un temps fini dans un état d’acceptation ou dans un état de refus ?
En vue de démontrer qu’une qu’une telle machine de Turing n’existe pas, autrement dit que certains énoncés sont indécidables, on s’intéresse au « problème de l’arrêt » :
La machine M appliquée à l’entrée X s’arrête-t-elle ?
Si ce problème était décidable, alors il existerait une machine de Turing A qui, appliquée au code de M et à X, rendrait au bout d’un temps fini son verdict : M appliquée à X s’arrête (ou pas).
On pourrait alors construire une autre machine de Turing, que l’on va appeler B, fonctionnant ainsi :
B s’applique à un code X d’une machine de Turing.
B appliquée à X rejette si la machine A appliquée à X et à X (= à X appliquée à X) accepte.
Sinon B accepte.
Donc B accepte X si A appliquée à X et à X rejette. Autrement dit si X rejette X (X appliquée à X ne s’arrête pas).
Et on pourrait alors appliquer la machine B à elle-même. mais on aurait alors : "B accepte B si B rejette B". Ce qui est absurde.
Conclusion : le problème de l’arrêt (d’une machine de Turing, mais également d’un ordinateur) est indécidable.

Supposons alors que l’on dispose d’un algorithme de décision pour l’arithmétique de Peano. Le problème de l’arrêt peut être formulé comme un énoncé du premier ordre (en utilisant les méthodes développées par Gödel), et cet énoncé serait alors résolu par l’algorithme de décision. Ce qui est absurde.


Jusqu’à présent, on a donné des exemples très "classiques" de machines de Turing. On va maintenant donner des exemples inédits.
Pourquoi l’assurance que ces exemples sont inédits ? Parce qu’ils découlent d’une approche différente (presque d’un détournement) de la machine de Turing.
La machine de Turing est un "modèle robuste" : on peut prendre un ou plusieurs rubans, autoriser ou pas l’état stationnaire de la tête de lecture, utiliser un alphabet à plus ou moins de symboles... Fondamentalement, cela ne change ni le potentiel de production ni la vitesse (à constante multiplicative près) de la machine de Turing.
Il est classique de prendre une machine de Turing à plusieurs rubans. On peut également réserver un de ces rubans à la sortie et le mettre en écriture seule.
On va considérer ici une machine à 2 rubans, dont le deuxième est un ruban de sortie en écriture seule.
La "dimension transgressive" consistera à utiliser comme ruban de sortie un ruban bi-dimensionnel et quatre options de déplacement (pour ce ruban) au lieu de deux.
Le résultat de cette machine de Turing n’est plus un mot, c’est une image matricielle (bitmap). [8]
Le logiciel Scratch permet d’implémenter assez facilement cette machine de Turing. On reprend les idées de l’implémentation précédentes et on ajoute un lutin ayant la forme d’un pixel, et que l’on peut estampiller. Voici le script de ce lutin :

On comprend que dans cette implémentation les mouvements de la tête de lecture vont être pilotés par envois de messages.

On peut alors par exemple construire une machine de Turing qui trace un rectangle à partir de la donnée de sa longueur et de sa largeur en unaire.
Voici le script du lutin d’initialisation :

Et voici le script d’un des états :

Par exemple, appliquée à l’entrée 18 & 9, la machine de Turing donne le résultat suivant (un rectangle 18 px $\times$ 9 px) :

Lien vers le fichier Scratch en ligne

Dans le même esprit, on peut tracer une spirale :

Lien vers le fichier Scratch en ligne

Le déplacement de la tête de lecture est un déplacement relatif, de type géométrie de la tortue.
On peut donner des versions "géométrie de la tortue" des deux machines de Turing précédentes.

Script du lutin traceur dans ces versions :


Rectangle unaire en géométrie de la tortue

Lien vers le fichier Scratch en ligne

Spirale en géométrie de la tortue

Lien vers le fichier Scratch en ligne

En adaptant légèrement le script du lutin traceur, on peut tracer la fractale du dragon [9] :

Lien vers le fichier Scratch en ligne

3) Complexité

Cette partie (non moins fondamentale) sera traitée dans un prochain article.


notes

[1adaptation et amélioration d’une machine polonaise conçue par Marian Rejewski appelée "Bombe cryptologique"

[2Yuri MATIYASEVICH démontrera en 1970 que le 10e problème de Hilbert n’admet pas de solution : il n’existe pas d’algorithme permettant de décider si une équation diophantienne arbitraire possède une solution entière.

[3D’autres axiomatiques avaient aussi été proposées pour définir le concept d’algorithme :

  • le calcul d’Alonzo CHURCH
  • les fonctions récursives de Kurt GÖDEL

[4Le théorème de MATIYASEVICH (voir note 2) en est une confirmation.

[5Dans cet exemple, il n’y a ni état d’acceptation ni état de rejet explicite. On peut considérer que qF est l’état d’acceptation et qu’il existe un état de rejet qui n’est jamais atteint.

[6Débranche !! ;D

[7C’est un peu moins évident, mais on peut alors concevoir une « machine de Turing universelle » qui émule n’importe quelle machine de Turing : à cette machine de Turing, on soumet le code d’une machine de Turing et un code d’entrée. La machine universelle fait alors les mêmes opérations et donne le même résultat que la machine de Turing codée s’appliquant au (deuxième) code d’entrée.

[8On pourra comparer cette machine de Turing à la machine de Post à sortie bi-dimensionnelle (onglet Post++) de l’article "Sous les pavés le calcul".
Cette machine de Post n’est pas une machine de Turing et son fonctionnement est radicalement différent, seule sa sortie étant de type ruban.
Cela étant, on peut noter, comme le rappelle Alain Busser dans cet article, qu’Emil Post, qui souffrait d’un syndrome maniaco-dépressif, prétend avoir inventé la machine de Turing en 1921 (donc 15 ans avant Turing) mais que sa femme aurait jeté ses brouillons durant un de ses séjours à l’hôpital...

[9On trouvera d’autres méthodes pour construire cette fractale dans cet article.

Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197