La machine de Turing


Introduction

La machine de Turing est un modèle de machine abstrait introduit en 1936 par le chercheur anglais Alan Turing dans un article fondateur intitulé On Computable Numbers, With An Application To The Entscheidungsproblem dans lequel il propose une réponse à une question posée 8 ans plus tôt par le célèbre mathématicien David Hilbert.


Le principe

La machine de Turing s'apparente à une machine à écrire disposant d'un ruban de longueur infini et sur lequel sont déposés des symboles, un par case, qui représentent les données.

Une tête de lecture est capable de lire les symboles, de les effacer, ou de les remplacer par d'autres. La tête de lecture peut se déplacer à droite (ou le ruban se déplace à gauche) ou à gauche (le ruban à droite).

Un listing d'instructions sommaires constitue le programme.

Chaque ligne d'instruction est constituée de 5 éléments :

  • le nom de l'étape actuelle ;
  • la valeur lue ;
  • la nouvelle valeur ;
  • le déplacement ;
  • le nom de la prochaine étape qu'il faudra exécuter.

Elaboration d'un programme

Pour écrire un programme, on symbolise chaque étape par un rond contenant le numéro d'étape : .

L'étape initiale est représentée de la manière suivante :

Une étape finale se représente avec un double cercle :


Entre les différentes étapes, les flèche orientées détaillent les actions à réaliser.


Exemple d'un programme de complémentation

Le programme doit permettre de complémenter un mot d'entrée.

    • On considère que la tête de lecture est placée sur le bit de poids le plus fort à l'étape 0.
    • Si le bit est à "0" on le passe à 1 dans l'étape 1. A l'étape 1, le bit sous la tête est à "1" et on décale la tête à droite.
    • Si le bit est à "1", il passera à 0et à l'étape 2, le bit étant à "1" on décale la tête à droite
    • S'il n'y a pas de caractère sous la tête le programme s'arrête à l'étape 3.



Ecriture d'un programme pour le simulateur de machine de Turing


On utilisera le simulateur accessible par ce lien : http://www.siloged.fr/cours/NSI/turing/turing.html

La syntaxe à utiliser est relativement simple et respecte quelques règles :

Syntaxe:

  • Chaque ligne doit contenir un tuple du formulaire [état actuel] [valeur courante] [nouvelle valeur] [déplacement] [prochain état].
  • Vous pouvez utiliser n'importe quel nombre ou mot pour [état actuel]et [prochain état], par exemple. 10, a, etat1. Les étiquettes d'état sont sensibles à la casse.
  • Vous pouvez utiliser n'importe quel caractère pour [valeur courante]et [nouvelle valeur], ou ' _' pour représenter une espace (espace). Les symboles sont sensibles à la casse.
  • [déplacement] doit être égal [l], [r] ou [*], indiquant respectivement "déplacer vers la gauche", "déplacer vers la droite" ou "ne pas bouger" la tête de lecture.
  • Tout ce qui se trouve après le caractère ';' est un commentaire et est ignoré.
  • La machine s'arrête lorsqu'elle atteint un état commençant par 'halt', par exemple. ''halt'', ''halt-accept''.


Formalisation de l'exemple de complémentation