Turmite
Cet article est une ébauche concernant les automates cellulaires.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion.
Ne doit pas être confondu avec Termite.
En informatique théorique, une turmite est une machine de Turing bi-dimensionnelle dont la « bande » consiste en une grille infinie dont chaque case (ou dans certains cas chaque nœud ou arête) peut être écrite ou effacée par une « tête » dont l'orientation change à chaque itération en fonction de l'état de la cellule où elle est située.
Le terme « turmite » fait référence en anglais à la fois à « Turing machine » (« machine de Turing ») et à « termite ». Une telle machine est également appelée « fourmi » lorsqu'elle utilise une grille de cases carrées (comme dans le cas de la fourmi de Langton) et une « abeille » ou un « ver » dans le cas d'une grille hexagonale (comme les vers de Paterson).
Histoire[modifier | modifier le code]
La fourmi de Langton a été inventée en 1986 et déclarée équivalente aux machines de Turing. Indépendamment, en 1988 Allen H.Brady a considéré l'idée des machines de Turing bidimensionnelles avec une orientation et les a appelées "TurNing Machines".
Apparemment, indépendamment de ces deux chercheurs, Greg Turk a étudié le même type de système et a écrit à A. K. Dewdney à ce sujet. Ce dernier les a nommés "Turmites" dans sa rubrique "Computer Recreations" de Scientific American en 1989
Rudy Rucker raconte l'histoire comme cela :
« Dewdney a rapporté qu'en cherchant un nom pour les créatures de Turk, il s'est dit : "Ce sont des machines de Turing étudiées par Turk, elles devraient donc s'appeler tur-quelque chose. Et comme elles ressemblent à de petits insectes ou à des mites, je les appellerai tur-mites ! Et ça ressemble à des termites ! Avec l'autorisation de Turk et Dewdney, je vais omettre le trait d'union et les appeler turmites. »
— Rudy Rucker, Laboratoire de la Vie Artificielle[1]
Turmites relatives et absolues[modifier | modifier le code]
Les turmites peuvent être catégorisées comme étant soit relatives ou absolues. Les turmites relatives égalemment connu sous le nom de "Turning machines" ont une orientation interne. La fourmi de Langton en est un exemple. Les turmites relatives sont par définition isotropes ; la rotation des turmites n'affecte pas son résultat. Les turmites relatives sont ainsi nommées parce que les directions sont codées par rapport à l'orientation actuelle, ce qui équivaut à utiliser les mots "gauche" ou "arrière".En revanche les turmites absolues encodent leurs directions en termes absolus : une instruction particulière peut demander à la turmite de se déplacer vers "le nord". Les turmites absolues sont des analogues bimensionnels des machines de Turing conventionnelles, et sont parfois appelées simplement "machines de Turing bidimensionnelles". Le reste de cet article concerne le cas relatif.
Spécifications[modifier | modifier le code]
La spécification suivante est spécifique aux turmites sur une grille carrée bidimensionnelle, le type de turmite le plus étudié. Les turmites sur d'autres grilles peuvent être spécifiées de manière similaire.
Comme pour la fourmi de Langton, les turmites effectuent les opérations suivantes à chaque pas de temps :
- tourner sur place (d'un multiple de 90°)
- changer la couleur de la case
- avancer d'une case.
Comme pour les machines de Turing, les actions sont spécifiées par une table de transition d'état listant l'état interne actuel de la turmite et la couleur de la cellule sur laquelle elle se trouve. Par exemple, la turmite représentée dans l'image en haut de cette page est spécifiée par la table suivante :
| Couleur actuelle | |||||||
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| Écrire la couleur | Tourner | État suivant | Écrire la couleur | Tourner | État suivant | ||
| État actuel | 0 | 1 | D | 0 | 1 | D | 1 |
| 1 | 0 | N | 0 | 0 | N | 1 | |
La direction à prendre est l'une des suivantes : G (90° à gauche), D (90° à droite), N (pas de virage) et U (180° demi-tour).
Exemples[modifier | modifier le code]
- Exemples de turmites à deux états et à deux couleurs sur un square grid, tous en partant d'une configuration vide:
-
Croissance en spirale. -
Production d'une route après une période de croissance chaotique. -
Croissance chaotique avec une texture particulière. -
Croissance avec une texture particulière à l'intérieur d'un cadre en expansion. -
Construction de la spirale d'or. -
Construction d'un diamant en croissance.
- Exemples de turmites avec plus d'états et de couleurs et sur des grilles non carrées:
-
Turmite bicolore à trois états produisant un motif fractale en forme de flocon de neige. -
Turmite tricolore à trois états sur une grille hexagonale, se développant de manière chaotique avec une texture distinctive avant d'être bloquée dans une boucle périodique après environ 194150 étapes.
À partir d'une grille vide ou d'autres configurations, les comportements les plus couramment observés sont la croissance chaotique, la croissance en spirale et la construction des routes. De rares exemples deviennent périodiques après un certain nombre d'étapes.
Jeu du castor affairé[modifier | modifier le code]
Allen H. Brady a cherché des turmites terminants (l'équivalent des castors affairés) et a trouvé une machine bicolore à deux états qui imprimait 37 fois 1 avant de s'arrêter, et une autre qui faisait 121 pas avant de s'arrêter[2]. Il a également considéré des turmites qui se déplaçaient sur une grille triangulaire, et a trouvé plusieurs castors affairés ici aussi.
Ed Pegg Jr. a envisagé une autre approche du jeu du castor affairé. Il a suggéré que les turmites puissent tourner, par exemple, à la fois à gauche et à droite, en se divisant en deux. Les turmites qui se rencontrent ensuite s'annihilent mutuellement. Dans ce système, un castor affairé est celui qui, à partir d'une seule turmite, dure le plus longtemps avant que toutes les turmites ne s'anéantissent les unes les autres[3].
Références[modifier | modifier le code]
- (en) Rudy Rucker, « Artificial Life Lab », sur sjsu.edu (consulté le ).
- Allen H. Brady, The Universal Turing Machine: A Half-Century Survey, Springer-Verlag, , 2nd éd., 237–254 p. (ISBN 3-211-82637-8), « The Busy Beaver Game and the Meaning of Life »
- Ed Pegg, Jr., « Math Puzzle » (consulté le )
Voir aussi[modifier | modifier le code]
Article connexe[modifier | modifier le code]
Liens externes[modifier | modifier le code]
- (en) Math Games: 2D Turing Machines (MAA Online)
- (en) Eric W. Weisstein, « Turmite », sur MathWorld
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Turmite » (voir la liste des auteurs).
