Simulateur de machine de Turing

Charger le simulateur, écrit en Java ; ce n'est pas une applet, le chargement utilise la technologie Java Web Start. A titre d'information, voici le code source.

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.

Les règles chargées au lancement de la machine sont celles d'un castor record pour une machine à cinq états. Cette machine s'arrête avec 4097 caractères (non blancs) écrits sur la bande ; l'arrêt de la machine ne survient qu'après exécution de 11 798 825 instructions. Voir le site d'Heiner Marxen pour tous les détails sur les castors (busy beavers).

Quelques exemples de programmes pour ce simulateur peuvent être consultés et téléchargés.

Bande : bi-directionnelle (mais pas tout à fait infinie, hélas). Par convention le point '.' remplace le caractère blanc.

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 (é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

signifierait : 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 instructions 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 détaille les règles exactes de codage et de résolution des conflits (lorsque plusieurs règles sont applicables simultanément) ; on peut même placer des points d'arrêt dans le programme, pour observer son comportement et/ou faire la chasse aux bugs.

Logiciels : comme toute machine, celle-ci est fournie avec un peu de soft : additionneur, crible d'Eratosthène, etc.