La machine de Turing

Abbréviations
Turing conçoit une machine pour explorer la notion de "nombre calculable". Une machine de Turing permet de générer une suite de 0 et de 1, qui exprime un nombre sous forme binaire.
Par convention, les nombres sont affichés de gauche à droite et les 0 1 générés par la machine représentent un nombre compris entre 0 et 1.
101101
1/21/41/81/161/321/64
1 0 1 1 0 1 représente 1*1/2 + 0*1/4 + 1*1/8 + 1*1/16 + 0*1/32 + 1*1/64

Une machine de Turing peut être vue comme une bande de papier infinie, qui est découpée en carrés. Chaque carré peut contenir un symbole. Machine de Turing Les cases de la bande de papier sont numérotées.

Pour chaque machine, on choisit les symboles qu'on va représenter.
La première machine fonctionne avec 3 symboles possibles : 0, 1 et None (case vide)

La machine est un automate qui ne peut faire que des choses très simples : Une m-config est constituée de : (voir exemple "Machine de Turing 1" plus bas)

Instructions possibles : Turing appelle configuration le couple (m-config courante, symbole courant).
La configuration détermine le comportement attendu de la machine.

MT1 - Machine de Turing 1

Reproduit fidèlement la première machine présentée dans l'article original de Turing.
Référence : [AT] p 81

Cette machine affiche indéfiniment 0 1 0 1 0 1 0 ... Machine de Turing m-configurations :
m-configCurrent symbolOperationsNext
b None P0, R c
c None R e
e None P1, R f
f None R b
Etat initial : Exécution : On peut se demander pourquoi laisser des cases vides entre 2 symboles 0 ou 1 affiché. Cela ne sert à rien pour cette machine, mais sera utile dans les machines suivantes.

TD Machine de Turing

But : Implémenter la machine MT1 dans un langage familier, puis la traduire en java
A partir de la table de m-config et d'une bande vierge, mettez vous à la place de MT1 pour écrire les symboles sur la bande en suivant les changements d'état de la machine (en imaginant, ou avec un papier et un crayon).
Faire l'inventaire des notions permettant de modéliser une machine de Turing ainsi que leurs relations.
Considérez le point suivant : on cherche à implémenter une machine qui puisse exécuter différentes configurations.
Si les instructions sont "codées en dur" (contenues dans le code), il faudra modifier le code pour chaque machine.
On va donc stocker les caractéristiques propres à chaque machine dans des fichiers de configuration, et le programme va prendre comme paramètre la configuration à exécuter.
Décrivez la structure des informations à mettre dans un fichier de configuration.
Prenez en compte le fait que les symboles écrits sur la bande sont spécifiques à chaque machine (par exemple, MT1 utilise 0 et 1, mais MT2 utilise aussi e et x). Les symboles possibles doivent donc faire aussi partie du fichier de configuration.
Ecrivez un fichier de configuration contenant les informations de configuration. Utilisez la syntaxe de votre choix ; on a besoin d'une syntaxe permettant d'exprimer des données structurées, comme json, yaml, xml, toml.

Implémentation

Ecrivez un programme qui implémente cette machine, dans le langage de votre choix.
Placez votre code et les configurations dans des répertories distincts (cela permet à plusieurs implémentations d'utiliser les mêmes configurations).
Le programme doit s'exécuter en mode console et prendre en paramètre : Ex :
php run-turing.php MT1 5
Fixez à 10 le nombre d'itérations par défaut (utilisé si le second paramètre n'est pas spécifié).
Le code proposé comme solution utilise la syntaxe yaml et est organisé de cette manière :
turing/
    ├── configs
    │   ├── MT1b.yml
    │   ├── MT1.yml
    │   └── MT2.yml
    ├── turing1-java
    │   ├── Machine.java
    │   └── RunTuring.java
    ├── turing1-php
    │   ├── Machine.php
    │   └── run-turing.php
    └── turing1-php-objet
        ├── Machine.php
        └── run-turing.php
Cette organisation permet à différentes implémentations d'utiliser les mêmes fichiers de configuration.
Conseils
Consignes
L'affichage pour les 5 premières étapes de MT1 doit être
=== run 0 - MConfig : b ===
Tape : |   |
         ^                                                                                                                                  
=== run 1 - MConfig : c ===
Tape : | 0 |   |
             ^                                                                                                                              
=== run 2 - MConfig : e ===
Tape : | 0 |   |   |
                 ^                                                                                                                          
=== run 3 - MConfig : f ===
Tape : | 0 |   | 1 |   |
                     ^                                                                                                                      
=== run 4 - MConfig : b ===
Tape : | 0 |   | 1 |   |   |
                         ^                                                                                                                  
=== run 5 - MConfig : c ===
Tape : | 0 |   | 1 |   | 0 |   |
                             ^

Changement de m-configurations

Turing donne ensuite une autre table de m-config qui fait exactement la même chose, mais différement : il y a une seule m-config et les opérations dépendent de Current symbol.
([AT] p 84)

Ob va appeler cette machine MT1b.
Complétez la table suivante, en indiquant les opérations à effectuer pour les différents cas (None, 0, 1).
(note : c'est très simple, plus simple que la première table).
m-configCurrent symbolOperationsNext
b None
0
1
à compléter
à compléter
à compléter
b
Ecrivez un fichier de configuration avec cette nouvelle table, et vérifiez que votre code l'exécute correctement.

Machine de Turing MT2

La seconde machine présentée par Turing ([AT] p 85) affiche la séquence
ə ə 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 ...
La séquence affichée est : Symboles d'initialisations ə ə 0 - un 0 - un 1 - un 0 - deux 1 - un 0 - trois 1 - un 0 - quatre 1 - etc.

Les symboles possibles sont : ə, 0, 1, x et None.
m-configCurrent symbolOperationsNext
b None Pə, R, Pə, R, P0, R, R, P0, L, L o
o 1
0
R, Px, L, L, L o
q
q 0 ou 1
None
R, R
P1, L
q
p
p x
ə
None
E, R
R
L, L
q
f
p
f 0 ou 1
None
R, R
P0, L, L
f
o
Schéma permettant de suivre pas à pas l'évolution de la machine. Les symboles écrits sur la bande sont encerclés. Les symboles effacés sont encerclés et barrés. Fonctionnement de la 2ème machine de Turing On peut se demander pourquoi mettre deux ə au début. Cela ne sert à rien pour cette machine, mais est utilisé dans les machines suivantes.
Exercice possible
Générer en SVG le schéma précédent.

TD Machine de Turing (suite)

Après avoir vu les implémentations php, analysez l'implémentation turing1-java
Cette implémentation a été implémentée "à la php", en utilisant des Maps. On peut voir que cette approche a ses limites en java : on ne peut pas typer correctement Machine.mconfigs.
En effet, pour traduire le contenu de la clé NONE de
mconfigs: 
  b: 
    NONE:
      operations: [P0, R]
      next: c
l'implémentation utilise comme type Map<String, Object>.
Impossible de faire plus précis que Object car ["P0", "R"] et "c" ne sont pas du même type.
On peut s'en rendre compte car javac fait un warning

Pour s'en sortir, on peut écrire une classe (MConfigEntry dans doc/turing-er1.svg), qui a 2 champs : operations et next.
Là, on pourra typer correctement.
  1. Suivez turing1-java/README pour installer yamlbeans
  2. Compilez le code
    javac -Xlint:unchecked -cp /path/to/yamlbeans/src:. RunTuring.java
    -Xlint:unchecked donne des détails sur ce problème de type
  3. Ecrivez une classe MConfigEntry, et adapter le constructeur de manière à utiliser cette classe.
  4. Adaptez Machine.runOneStep() pour utiliser MConfigEntry.
Exercice possible
Ecrire une application swing où Machine.toString() est affichée dans une zone de texte.
En utilisant un timer (par exemple avec Thread.sleep()), reproduisez le comportement du mode DISPLAY_ANIME de l'implémentation php.