Simulateur de machine de Turing

Charger la version 2 du simulateur, écrite en Java ; ce n'est pas une applet, c'est une archive Java (fichier jar), qu'il faut télécharger et exécuter avec votre machine virtuelle Java (Java runtime) préférée. Note : avant la première exécution il faut peut-être rendre le fichier ... exécutable, en modifiant les droits d'accès, avec une commande du genre chmod +x (sous Unix).

Exécution : utiliser les boutons Play / Pause, etc. La réglette située sur la gauche du tableau de bord permet de régler la vitesse d'exécution ; la vitesse la plus lente correspond à l'exécution d'une transition par seconde, ensuite chaque déplacement du curseur d'un cran vers la droite multiplie la vitesse par deux, à l'exception de la vitesse la plus rapide : dans ce cas l'affichage n'est plus rafraîchi après chaque transition, mais après chaque exécution d'un million (environ) de transitions.

Le bouton à droite de Play / Pause permet d'exécuter une seule instruction, c'est le mode pas à pas. Le troisième bouton permet de "rembobiner le film", c'est à dire de revenir à la configuration initiale.

Les règles chargées au lancement de la machine sont celles d'un castor record pour une machine à cinq états. L'alphabet comporte un seul caractère en plus du blanc, initialement la bande est blanche, or cette machine s'arrête avec 4097 caractères (non blancs) écrits sur la bande, et après exécution de 11 798 825 transitions. Son principe est le suivant : elle calcule une suite géométrique un de raison 5/3, codée par le nombre de x écrits sur la bande, et s'arrête lorsque un vaut 2 modulo 3. La suite est suffisamment bien choisie pour que ceci ne se produise pas avant n = 14, tout en utilisant seulement cinq états, y compris pour amorcer le calcul !

Voir le site d'Heiner Marxen pour tous les détails sur les castors (busy beavers), c'est un programme écrit par lui qui a découvert la machine présentée ici.

Quelques exemples de programmes (additionneur, crible d'Eratosthène, etc.) sont disponibles pour ce simulateur ; ce sont de simples fichiers de texte, qu'on peut exécuter après les avoir copiés/collés dans le panneau du programme.

Bande : bi-directionnelle (mais pas tout à fait infinie, hélas). Le point '.' remplace le caractère blanc, c'est indispensable pour écrire les règles correspondantes, voir ci-dessous. 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, cf. le mode d'emploi détaillé.

Programme : constitué d'un ensemble de règles (on dit aussi transitions ou tout simplement instructions), une par ligne, dans le panneau droit. 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 les règles :

1 . 2 x Left
2 x 2 x Right
2 x 2 - R

doivent être interprétées comme suit :

Pour éviter d'écrire plusieurs règles similaires, le tiret '-' peut aussi remplacer le caractère lu, et signifie alors autres cas ; par exemple le fragment suivant :

10 - 10 - Droite
10 # 20 - D

signifie rester dans l'état 10 et déplacer la tête à droite, jusqu'à trouver le marqueur '#' ; passer alors dans l'état 20, etc. Comme on le voit, les déplacements de la tête de lecture peuvent être indiqués en français ou en anglais, abrégés ou non.

Pour entrer ou modifier un programme, il suffit d'éditer les règles situées dans la fenêtre droite. Appuyer sur l'un des boutons d'exécution provoque la relecture automatique du programme : toute modification apportée à celui-ci est donc immédiatement prise en compte. Pour charger ou sauvegarder un programme, utiliser simplement copier-coller à partir d'un fichier texte, seul un retournement de la demande sur le marché pourrait me conduire à ajouter au simulateur un menu pour lire ou écrire dans un fichier :-)

Un document complète le présent mode d'emploi : il détaille comment sont résolus les conflits (lorsque plusieurs règles sont applicables simultanément), comment initaliser la machine, etc. Noter qu'on peut même placer des points d'arrêt dans le programme, pour observer son comportement et/ou faire la chasse aux bugs.