La machine de Turing

En 1936, Alan Turing présente sa « machine » théorique afin de répondre à un défi mathématique lancé 36 ans plus tôt.

I Fonctionnement de la machine de Turing

1 Description de la machine

Le premier élément est un ruban ayant un commencement mais une longueur infinie et qui représente la mémoire d’un ordinateur (qui, elle, est finie). Le second élément est une tête de lecture qui lit, écrit et se déplace sur le ruban.

Il faut s’imaginer une machine de Turing comme ceci par exemple :

Machine de Turing

Un □ symbolise une case « blanche » et occupe la première case. Il est suivi par des 0 et des 1. Une autre case blanche marque la fin de la chaîne.

L’ensemble des symboles {0 ; 1 ; □} forme un alphabet.

Le pointeur indique au départ la première case.

Il est possible d’effectuer trois actions qui dépendent de l’état du pointeur et du caractère pointé :

• changer l’état du pointeur ;

• changer le caractère pointé sur le ruban ;

• déplacer le pointeur d’une case vers la gauche ou vers la droite.

2 Exemple de programme sur la machine de Turing

Imaginons que nous voulions, par exemple, changer les 0 en 1 et vice-versa puis remettre le pointeur dans sa position initiale.

L’algorithme serait donc :

• lorsque le pointeur rencontre le premier blanc, il se déplace vers la droite ;

• chaque fois que le pointeur rencontre un 0 ou un 1, il le change en son complémentaire et se déplace vers la droite ;

• lorsqu’il rencontre le deuxième blanc, il recule d’une case vers la gauche jusqu’à ce qu’il rencontre le premier blanc.

Ceci constitue un algorithme que nous pouvons représenter par l’automate suivant :

• Les cercles correspondent aux différents états de la machine : il y en a trois. Les flèches décrivent, elles, les actions accomplies par la machine.

• La flèche entrante en $q_0$ indique qu’il s’agit de l’état initial. Le double cercle autour de $q_2$ indique qu’il s’agit de l’état final.

• Une flèche allant de $q_i$ à $q_j$ surmontée d’un couple $a\text{/}b,c$ signifie que si la machine est dans l’état $q_i$ et qu’elle pointe sur une case contenant $a$ alors elle remplace $a$ par $b$ et bouge d’une case vers la direction indiquée par $c$ : gauche (G), droite (D), reste sur place (R).

On voit qu’un nombre fini d’instructions permet de traiter une chaîne de longueur aussi longue que l’on veut.

II Complexité

Ce modèle sert en particulier d’étalon pour mesurer la complexité d’un algorithme : c’est l’ordre de grandeur du nombre d’actions élémentaires (lire, déplacer la tête de lecture) qu’effectuerait une machine de Turing pour exécuter l’algorithme.

Un algorithme formel est la description d’une machine de Turing. Même si cela apparaît fastidieux, la modélisation d’un algorithme par une machine de Turing permet de répondre à trois questions fondamentales :

• Est-ce que l’algorithme va se terminer ? (Est-il « calculable » ?)

• Quelle est « l’efficacité » en temps d’un algorithme pour traiter des données ? Cela revient à savoir combien de mouvements la tête de lecture va effectuer.

• Quelle place en mémoire va demander l’exécution de l’algorithme ? Cela revient à compter le nombre de cases du ruban nécessaires.

Dans la pratique, il serait trop fastidieux de traduire tous les algorithmes en machines de Turing. On se contente plutôt de décomposer l’algorithme en « opérations élémentaires » de complexité constante : une opération arithmétique sur un flottant, une comparaison entre deux nombres, etc.