Attention !

Sur cette page le simulateur de machine de Turing est une applet Java, qui est donc exécutée par votre navigateur. Si vous souhaitez vraiment utiliser ce simulateur pour écrire et/ou tester des programmes, il vaut probablement mieux consulter cette page, qui vous permettra de télécharger la version 2 du simulateur sous forme d'application indépendante (archive jar). Cette seconde version comporte quelques améliorations, et comme c'est une application indépendante, sa fenêtre peut être redimensionnée, de même que le panneau qui contient le programme.

Applet

Code source

Test : cliquer sur le bouton Automatique ; si rien ne se passe, le navigateur est probablement dépourvu d'une machine virtuelle Java pour l'environnement Java 2, et il faut télécharger le plug-in approprié.

Modes : la machine peut fonctionner en mode Automatique ou Pas à pas, grâce aux boutons ad hoc.

La petite fenêtre numérique située à droite du bouton Automatique indique le délai, en millisecondes, qui sépare l'exécution de deux instructions, pour permettre la mise à jour de l'affichage ; le réglage par défaut (100) correspond donc à dix instructions par seconde. Si le délai est ramené (manuellement) à zéro, l'affichage est réactualisé après chaque exécution d'un million d'instructions.

La petite fenêtre numérique située à droite du bouton Pas à pas indique le nombre d'instructions exécutées depuis le lancement de la machine. Ce champ peut lui aussi être modifié manuellement, par exemple pour le remettre à zéro.

Bande : bi-directionnelle, mais pas tout à fait infinie, hélas : ses dimensions sont fournies par les paramètres bande et origine de la balise <APPLET>, voir le code source de cette page pour un exemple. Le paramètre bande indique la longueur totale de la bande (10000 par défaut, c'est-à-dire en l'absence de spécification dans la balise <APPLET>), et le paramètre origine indique la position de celle-ci sur la bande : sa valeur par défaut est 1000, ce qui signifie que les 1000 premières cases de la bande apparaissent avec une abscisse négative aux yeux de l'utilisateur.

La bande est blanche au départ, mais par convention le caractère '.' (point) remplace le caractère blanc. Pour écrire sur la bande, cliquer dessus si nécessaire (attention à ne pas écrire par inadvertance dans la fenêtre du programme), puis taper les caractères. Pour faire défiler la bande, idem en utilisant les touches de déplacement horizontal du curseur.

L'ajout de règles temporaires dans le programme reste la méthode la plus générale pour manipuler la bande, par exemple pour se déplacer vers un caractère, ou un motif, précis.

Programme : constitué d'un ensemble de règles, une par ligne, dans la fenêtre droite. Chaque règle est composée de cinq items, séparés par un ou plusieurs blancs :

q c q' c' d

q est l'état de la machine, c le caractère lu, q' le nouvel état, c' le caractère écrit, et d le déplacement.

Un état doit être un nombre entier, l'état initial est l'état 0, il n'y a pas d'autre restriction (en particulier les états ne sont pas nécessairement de petits entiers consécutifs). Il n'y a pas de restriction sur les caractères utilisables, sauf les trois conventions indiquées ci-dessous. Un déplacement à gauche peut être indiqué par tout mot commençant par 'g', 'l' (left), '<' ou '-' (tiret) ; l'absence de déplacement est codée 's' (stationnement) ou '=' ; le reste est interprété comme un déplacement à droite.

Appuyer sur l'un des deux boutons d'exécution Automatique ou Pas à pas, provoque la relecture du programme : toute modification apportée au texte de la fenêtre est donc immédiatement prise en compte.

Pour charger ou sauvegarder un programme, utiliser simplement copier-coller à partir d'un fichier de texte. On peut ajouter des commentaires, soit en commençant la ligne par '//', soit en fin de règle, après les cinq items.

L'ordre des règles est sans importance, sauf si plusieurs règles ont la même partie gauche (q, c), auquel cas c'est la dernière règle qui est prise en compte. Ajouter de nouvelles règles en fin de programme permet ainsi de modifier temporairement son comportement.

Points d'arrêt : si le nouvel état (troisième item d'une règle) est négatif, la machine (en mode automatique) 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.

Caractères spéciaux :

Logiciels fournis : comme toute machine, celle-ci est fournie avec du logiciel.

Les règles chargées au lancement de la machine sont celles d'un castor record pour une machine à cinq états (sans compter l'état final, ici 0). Cette machine écrit 4098 caractères sur la bande et exécute 11 798 826 instructions avant de s'arrêter (sans compter une instruction artificielle en début de programme, pour passer de l'état 0 à l'état 1). Voir le site d'Heiner Marxen pour tous les détails sur les castors (busy beavers).

Un crible d'Eratosthène calcule les nombres premiers inférieurs ou égaux à n, alors qu'une machine de Turing est dépourvue d'instructions arithmétiques. Mode d'emploi : écrire n caractères (quelconques) sur la bande (commencer à la position 1, et non 0, pour éviter un décalage déconcertant lorsqu'on examine les réultats en fin d'exécution du programme), puis lancer l'exécution (la position initiale du curseur est donc juste à droite du dernier caractère écrit, autrement dit c'est la position n+1). Lorsque la machine s'arrête, les positions des nombres premiers sont marquées 'b' sur la bande, sauf une, marquée 'c', qui correspond au plus petit entier premier p tel que p2>n.

Remerciements : le graphisme de la machine est emprunté au site de la Java cup, qui contient une machine beaucoup plus amusante que celle-ci (et sonorisée), mais peu utilisable en pratique, à mon avis.