Récréation

Une machine de Turing est une machine abstraite qui passe d'un état à un autre en suivant un ensemble de lois précises lorsqu'elle lit un caractère sur une bande. Cette machine peut imprimer ou effacer des symboles sur la bande.
Cette applet présente une machine de Turing dotée des lois suivantes :
Un curseur se déplace le long d'une bande qui contient des 0 et des 1.
On n'examine en dehors de la case pointée par le curseur que les deux cases précédentes et les deux cases suivantes. (fenêtre de 5 cases entraînée par le curseur)
La configuration 00100 devient (après passage) 00000    (suppression)
La configuration 00010 devient  00110    (création)
La configuration 01000 devient  01100    (création)
La configuration 00101 devient  00001    
La configuration 10100 devient  10000.
Une case qui contient un 1 reste avec un 1 si aucune des 5 règles ne s'applique.
Les deux premières cases du ruban et les deux dernières sont omises lors du déplacement du curseur sur le ruban. (Comme les règles sont symétriques, le sens du déplacement est indifférent).
Chaque ligne de l'affichage (les 1 sont représentés par une case rouge) correspond à un passage de la machine. Chaque ligne sert d'état initial pour le passage suivant.
La superposition des différents états de la machine donne des motifs assez esthétiques.

L'applet permet de modifier la position de la case rouge initiale, la distance entre deux cases rouges et la longueur du ruban.
Les configurations suivantes donnent des représentations intéressantes :
6, 8, 61;    5, 5, 61;    5,10, 61;    8, 15, 62; 4, 4, 61; 6, 16, 19;
Trouvez d'autres configurations
Essayez de faire marcher cette machine avec du papier et un crayon.

TURING Alan Mathison (1912-1954) Ingénieur et mathématicien anglais.

J'ai trouvé la description de cette machine dans :
Requiem pour une puce par Gérard RAMSTEIN (Seuil 2001) ISBN 2.02041941.6.
Dans ce roman pseudo policier l'auteur présente de manière humoristique l'histoire de l'informatique.