Fourmi de Langton

Une fourmi qui pivote sur des cases colorées et construit une autoroute répétitive après une phase chaotique.

  • Ant
  • Turn right
  • Turn left
100%

Tap to drop another ant, drag to paint tiles in its way; Rerun starts again from step 0 with the ants and tiles you added. One ant turns, flips the tile and steps, and after about 10,000 steps builds an ordered highway.

Setup
120 × 120 cells
Model
View
60 steps per second
40°

Que pensez-vous de Fourmi de Langton ?

À propos de Fourmi de Langton

Invention
1986, par Christopher Langton
Règles
Droite sur blanc, gauche sur noir ; inverser la cellule ; avancer
Autoroute
Apparaît après environ 10 000 étapes et boucle tous les 104 pas
Préréglages
RL, RLR, LLRR et trois règles multicolores étendues
Vitesse
Jusqu'à 400 étapes par image

La Fourmi de Langton est une machine de Turing bidimensionnelle inventée par Christopher Langton en 1986. Posée sur une grille de cellules blanches et noires, elle obéit à deux règles : sur une cellule blanche elle tourne à droite, sur une cellule noire elle tourne à gauche ; dans les deux cas, elle inverse la couleur de la cellule puis avance d'un pas. Rien d'autre n'intervient.

Pendant les premières centaines de pas, la fourmi dessine des formes simples et presque symétriques. Elle erre ensuite de manière chaotique pendant environ 10 000 étapes, avant de construire une autoroute : une trajectoire diagonale de 104 pas qui se répète indéfiniment. Toutes les configurations initiales testées finissent par produire une autoroute, mais aucune preuve mathématique générale n'existe. Les versions généralisées utilisent une chaîne de règles plus longue, attribuant une lettre par couleur, et produisent des triangles, des motifs symétriques ou des blocs pleins réguliers.

Ce simulateur gère une ou plusieurs fourmis jusqu'à 400 pas par image. Choisissez un préréglage tel que Classic highway (RL), Triangles (RLR), Symmetry (LLRR), Cardioid, Chaos ou Filled, ou saisissez votre propre séquence de virages R, L, U et N. Cliquez pour ajouter des fourmis, tracez des obstacles sur leur chemin, réglez la grille et exportez en PNG.

Comment utiliser Fourmi de Langton

  1. Démarrer la fourmi. Cliquez sur Play pour observer la fourmi RL classique : formes simples d'abord, puis chaos, puis autoroute diagonale vers 10 000 pas.
  2. Accélérer le calcul. Augmentez Steps per frame jusqu'à 400 pour atteindre l'autoroute rapidement.
  3. Tester d'autres règles. Choisissez un préréglage comme Triangles, Symmetry ou Cardioid, ou saisissez une Rule avec R (droite), L (gauche), U (demi-tour) et N (tout droit).
  4. Interagir. Cliquez sur la grille pour ajouter des fourmis ou glissez pour peindre des cases sur leur passage et observer leurs réactions.
  5. Exporter. Ajustez Grid, Hue et Background, puis mettez en pause pour faire un export PNG.

Foire aux questions

Quelles sont les règles de la fourmi de Langton ?

Sur une case blanche, tourner de 90° à droite ; sur une case noire, tourner de 90° à gauche. Inverser la couleur de la case et avancer d'une case. Ce sont les deux seules règles.

Qu'est-ce que l'autoroute ?

Après environ 10 000 pas d'un comportement apparemment chaotique, la fourmi classique entre dans un cycle régulier de 104 étapes qui la déplace de deux cases en diagonale à chaque répétition, laissant une piste droite infinie appelée autoroute.

La fourmi construit-elle toujours une autoroute ?

Toutes les configurations de départ testées jusqu'ici aboutissent à une autoroute, mais cela n'a jamais été formellement démontré. Il est en revanche prouvé que sa trajectoire n'est pas bornée : elle ne peut rester confinée dans un espace fini.

Que signifient les lettres dans les règles comme RLR ?

Chaque lettre correspond à la direction prise sur une couleur donnée, les couleurs défilant en boucle à chaque passage. RL correspond à la version classique bicolore ; les chaînes plus longues utilisent davantage de couleurs, avec U pour demi-tour et N pour continuer tout droit.

Guides

Références

  1. Langton, C. G. (1986). Studying artificial life with cellular automata. Physica D 22(1–3), 120–149.