La machine de Turing | CNAM 2ISA Millau

Abbréviations

[AT] : Livre The annotated Turing (Charles Petzold, 2008)
MT : Machine de Turing

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,
les 0 1 générés par la machine représentent un nombre compris entre 0 et 1.

1	0	1	1	0	1
1/2	1/4	1/8	1/16	1/32	1/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.

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 :

Elle a une tête de lecture qui pointe sur le carré courant qui contient le symbole courant.
Elle peut lire, écrire ou effacer le symbole courant.
Elle peut changer de carré courant (aller à droite ou à gauche).
Elle peut se trouver dans un certain nombre d'états, que Turing appelle m-configurations.
A chaque instant, elle se trouve dans un état, l'état courant (ou la m-config courante).

Une m-config est constituée de :

Nom de la m-config
Instructions à exécuter, dépendant du symbole courant
Nom de la m-config suivante

(voir exemple "Machine de Turing 1" plus bas)

Instructions possibles :

R : Go Right (change current square)
L : Go Left (change current square)
P : Print
- P0 : Print 0
- P1 : Print 1
E : Erase = Print None

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-config	Current symbol	Operations	Next
b	None	P0, R	c
c	None	R	e
e	None	P1, R	f
f	None	R	b

Etat initial :

m-config = b
la tête de lecture est sur le carré n° 0

Exécution :

On démarre sur la première case dans l'état b.
Execution des opérations de b : P0 = Ecrit 0 dans la case courante ; R = va vers la droite ; va vers l'état c
Execution des opérations de c : R = va vers la droite ; va vers l'état e
Execution des opérations de e : P1 = Ecrit 1 dans la case courante ; R = va vers la droite ; va vers l'état f
Execution des opérations de f : R = va vers la droite ; va vers l'état b

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. On a besoin d'une syntaxe permettant d'exprimer des données structurées, comme json, yaml, xml, toml.
Utilisez YAML ; voir cette page.

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 :

La configuration utilisée par la machine
Optionnelement, nombre d'itérations que la machine doit exécuter

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

Séparez le code qui implémente la machine du code qui gère les paramètres et déclenche l'exécution de la machine.

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-config	Current symbol	Operations	Next
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.

ə se nomme "schwa", et sert de "sentinelle", pour marquer le début de la séquence.
1 est utilisé pour marquer les "mots" (séries de 1).
0 sert de séparateur entre les mots.
x sert de marqueur, pour "compter" le nombre de 1 écrits dans la dernière séquence.

m-config	Current symbol	Operations	Next
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

Fonctionnement de la 2ème machine de Turing

b sert à initialiser la machine, et n'est appelé qu'une seule fois.
q et f bouclent sur eux même pour aller à droite jusqu'à la position du prochain 0 ou 1 à imprimer. q affiche un 1 et f affiche un 0.
q écrit des 1 ; il est à la fois déclenché par p et par o
f écrit un 0, qui sépare deux séries de 1.
f passe la main à o, qui va à reculons (vers la gauche) et écrire des x dans les cases intermédiaires tant qu'il trouve des 1.
Il y a donc autant de x que de 1 écrits lors de la dernière série de 1.
o passe à q, qui va écrire le premier 1 d'une nouvelle série.
p se déplace sur les cases intermédiaires. Il recule tant qu'il trouve des cases vides. Quand il tombe sur x, il l'efface et repasse à q pour écrire un 1.
S'il ne rencontre pas de x, il recule jusqu'au début et passe la main à f pour imprimer un nouveau 0.

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

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.

Suivez turing1-java/README pour installer yamlbeans
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
Ecrivez une classe MConfigEntry, et adapter le constructeur de manière à utiliser cette classe.
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.