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

Règles

Chaque règle est composée de cinq items (état, caractère lu, nouvel état, caractère écrit, déplacement de la tête de lecture), séparés par un ou plusieurs blancs ; par exemple :

10 a 20 b Left

signifie que si la machine est dans l'état 10 et lit un a, elle passe dans l'état 20, écrit un b, et déplace la tête de lecture à gauche.

La machine est déterministe, en cas de conflit (règles dont les deux premiers items sont identiques), c'est tout simplement la dernière règle (celle située le plus bas dans le programme) qui est exécutée. Outre qu'il est ainsi inutile d'ajouter quoi que ce soit au code Java du simulateur pour traiter les conflits (une nouvelle règle écrase simplement la précédente), cette convention permet à l'utilisateur de tester une modification du code, sans effacer l'ancien, en ajoutant de nouvelles règles à la fin.

Une règle dont le second item (caractère lu) est un caractère spécifique, comme a, x, '.' (blanc) etc. est toujours prioritaire sur une règle dont le second item est un tiret '-'. Autrement dit le code :

10 - 10 - Droite
10 # 20 - D

qui signifie dans l'état 10, déplacer la tête de lecture vers la droite jusqu'à lire un '#', et passer alors dans l'état 20, est équivalent au même code avec l'ordre des lignes inversé :

10 # 20 - D
10 - 10 - Droite

Initialisation

Une ligne du programme qui commence par Init (majuscules ou minuscules sont sans importance, en fait le simulateur teste simplement si la première lettre est un I ou un i) définit la configuration initiale, les trois items suivants doivent être un mot u, un entier q, et un second mot v, interprétés comme suit : la machine démarre dans l'état q, avec uv écrit sur la bande, et la tête de lecture est placée sur le premier caractère de v. Exemple:

Init ab 10 xba

signifie que la machine démarre dans l'état 10, avec abxba écrit sur la bande, et la tête de lecture est placée sur le caractère x. L'un des mots peut être blanc, la ligne :

init . 0 ab

signifie que la machine démarre dans l'état 0, avec ab écrit sur la bande, et que la tête de lecture est placée sur le caractère a. Ne pas oublier qu'un mot blanc est une suite de '.' (un seul suffit). Dernier exemple, la ligne :

Initial ab 1 .

signifie que la machine démarre dans l'état 1, avec ab écrit sur la bande, et que la tête de lecture est placée juste après le b.

Si aucune ligne du programme ne commence par I ou un i, la bande est initialement blanche, et l'état initial est 0. Le bouton le plus à droite "rembobine le film", c'est à dire restaure la configuration initiale.

Etats

Un état doit être un nombre entier positif ou nul (sauf dans le cas décrit ci-après), il n'y a pas d'autre restriction, en particulier les états ne sont pas nécessairement de petits entiers consécutifs.

Les états négatifs jouent un rôle tout à fait exceptionnel, ils permettent d'introduire des points d'arrêt dans le programme, ce qui, convenez-en, est tout à fait rare chez les machines de Turing. Si dans une règle le nouvel état (troisième item de la règle) est négatif, la machine s'arrête, après exécution d'une pseudo-instruction qui change simplement le signe de l'état, qui redevient donc positif. Il est ainsi facile, en intervenant directement dans la fenêtre du programme, d'ajouter ou de supprimer des points d'arrêt. Exemple :

1 . 2 x Left
2 . -3 x Right
3 . 1 x L
4 . 1 x L
1 x 1 - L
2 x 2 - R
3 x 4 - R
4 x 5 - R
5 x 3 . R

Dans la deuxième de ces règles, qui sont celles du castor chargé initialement avec la machine, on a introduit un signe '-' devant le '3', ce qui suffit pour stopper l'exécution dès que cette règle est exécutée, essayez ! Quand vous en avez assez, effacez délicatement ce signe '-', et vous aurez supprimé le point d'arrêt. Ah si les outils de debug étaient toujours aussi simples !

Bande

On peut utiliser le clavier pour écrire directement sur la bande, ou pour la faire défiler (touches de déplacement horizontal du curseur). Il vaut mieux que la machine soit à l'arrêt pendant ces opérations :-)

Attention : si l'arrêt de la machine ne provient pas de l'utilisation du bouton Pause, il arrive fréquemment que la zone de saisie active (focus) soit le panneau du programme, il faut alors appuyer sur un bouton (de préférence le plus inoffensif, celui du mode pas à pas) avant d'utiliser le clavier pour faire défiler la bande ou écrire dessus ; sinon on modifie par inadvertance le programme, ce qui donne souvent des résultats déplaisants.

De même, si la zone de saisie active est la réglette de vitesse, les touches de déplacement horizontal du curseur, sur le clavier, agissent sur la réglette et non sur la bande ; comme précédemment, il suffit d'appuyer sur le bouton du mode pas à pas pour qu'ensuite ces touches fassent défiler la bande.

La bande n'est hélas pas infinie, le caractère spécial '!' est écrit aux abords de ses extrémités gauche et droite, et joue le rôle de butée : comme le programme ne contient pas de règle de traitement de ce caractère (du moins on l'espère, d'ailleurs s'il en existait une elle serait ignorée), la machine s'arrête si elle arrive dans ces parages. Atteindre les limites de la bande est souvent le signe d'une erreur de programmation, et pour apercevoir la butée droite il suffit de lancer le programme suivant et de patienter (ou de choisir la vitesse maximale sur la réglette) :

Init . 10 .
10 . 10 - Right

On espère que l'utilisateur saura comment déplacer ensuite la tête de lecture sur la butée gauche :-) Bref ces butées évitent de perdre le contrôle de la machine, même avec une bande finie.

Divers

Documentation ultime

La complète vérité est évidemment dans le code source !