À propos de la fourmi de Langton | Autoroute, règles et turmites

Les règles

La fourmi parcourt une grille infinie de cases. Chaque case est blanche ou noire, et la fourmi regarde vers le nord, l’est, le sud ou l’ouest. La couleur sous ses pattes décide de tout le mouvement suivant. Sur une case blanche, elle tourne de 90° à droite (sens horaire), peint la case en noir et avance d’une cellule. Sur une case noire, elle tourne de 90° à gauche (sens antihoraire), peint la case en blanc et avance d’une cellule. Il n’y a aucun hasard. Lancez deux fois le même départ et vous obtenez la même image.

Trois phases

Lancez la fourmi sur une grille blanche vide et son comportement se divise en trois périodes bien connues. 1. Simplicité et symétrie, du pas 1 jusqu’au pas 500 environ. La traînée est petite et souvent symétrique. 2. Chaos, du pas 500 environ au pas 10 000 environ. La fourmi est prise dans son propre chemin. L’image ressemble à du bruit, alors que chaque pas est fixé d’avance. 3. L’autoroute, après environ 10 000 pas. La fourmi se verrouille dans un cycle de 104 pas. Chaque cycle ajoute un bloc diagonal répétitif et décale la fourmi de deux cellules sur le côté et de deux cellules vers l’avant. Une fois ce cycle lancé sur une grille libre, il continue pour toujours, et la fourmi construit une autoroute droite à partir du chaos.

Pourquoi c’est important

La fourmi est l’une des démonstrations les plus claires de l’émergence : une structure compliquée et difficile à prévoir naît d’une poignée de règles locales. Elle est aussi Turing-complète. Avec un motif de départ adapté, le même type de règle peut effectuer n’importe quel calcul qu’un ordinateur universel peut faire. Nul besoin de cette mécanique pour apprécier l’image. L’autoroute est déjà la surprise.

Couleurs, colonies, hexagones et turmites

L’idée a été étendue dans plusieurs directions. Les règles multicolores remplacent le noir et le blanc par une liste de virages, écrite sous forme de chaîne de L et de R. RL est la fourmi classique. RLR, LLRR et LRRRRRLLR donnent à chaque couleur son propre virage. La fourmi écrit la couleur suivante de la liste, et certaines de ces règles font pousser des figures géométriques symétriques au lieu d’une seule autoroute. Plusieurs fourmis partagent une même grille. Quand leurs traînées se croisent, elles peuvent couper une autoroute ou tisser un motif qu’aucune fourmi ne construirait seule. Une grille hexagonale donne six directions à la fourmi. Un virage à droite ou à gauche fait alors 60° au lieu de 90°. Un turmite garde un état interne, une petite mémoire. Le virage et la couleur écrite dépendent à la fois de la cellule et de cet état, si bien que la règle elle-même change pendant que la fourmi avance. Spirale, Tissage et Dérive dans l’application sont des turmites à deux états et deux couleurs.

Explorez-la dans PictorX

Ouvrez Fourmi de Langton pour lancer la fourmi classique, sauter dans la phase chaotique ou démarrer sur l’autoroute. Saisissez une règle de virage, ajoutez des fourmis, passez la grille en hexagones ou choisissez un turmite. Faites glisser pour vous déplacer, faites défiler pour zoomer, peignez des cellules et déposez d’autres fourmis. Enregistrez un PNG ou ouvrez le canevas dans l’éditeur PictorX. Associez-la à la Conjecture de Collatz ou au Labo de réaction-diffusion pour d’autres règles simples aux images surprenantes.

Questions fréquemment posées

Qui a inventé la fourmi de Langton ?

Chris Langton, en 1986. C’est une machine de Turing à deux dimensions : une fourmi, une grille infinie et un virage qui dépend uniquement de la couleur de la cellule courante.

Tout motif de départ construit-il une autoroute ?

La grille vide, oui, après environ 10 000 pas, et le cycle de 104 pas se poursuit une fois la fourmi sur cette autoroute. D’autres motifs de départ et d’autres règles peuvent construire des autoroutes, rester bornés ou croître sous une autre forme. Le favori « Autoroute » de l’application place la fourmi classique juste après le début du cycle.

Que signifie la chaîne de règle ?

Chaque caractère est le virage pour une couleur. R signifie tourner à droite, L tourner à gauche. Après le virage, la fourmi fait passer la cellule à la couleur suivante et avance. RL correspond au noir et blanc. Une chaîne plus longue donne une fourmi multicolore.

En quoi un turmite diffère-t-il de la fourmi ?

La fourmi classique n’a aucune mémoire en dehors de la grille. Un turmite possède en plus un état interne. La couleur de la cellule et cet état choisissent ensemble la couleur écrite, le virage et l’état suivant.