Fourmi de Langton

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources ().

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

On nomme fourmi de Langton un automate cellulaire (voir machine de Turing) bidimensionnel comportant un jeu de règles très simples. On lui a donné le nom de Christopher Langton, son inventeur.

Elle constitue l'un des systèmes les plus simples permettant de mettre en évidence un exemple de comportement émergent.

Règles

Les cases d'une grille bidimensionnelle peuvent être blanches ou noires. On considère arbitrairement l'une de ces cases comme étant l'emplacement initial de la fourmi. Dans l'état initial, toutes les cases sont de la même couleur.

La fourmi peut se déplacer à gauche, à droite, en haut ou en bas d'une case à chaque fois selon les règles suivantes :

  • Si la fourmi est sur une case noire, elle tourne de 90° vers la gauche, change la couleur de la case en blanc et avance d'une case.
  • Si la fourmi est sur une case blanche, elle tourne de 90° vers la droite, change la couleur de la case en noir et avance d'une case.

Il est également possible de définir la fourmi de Langton comme un automate cellulaire où la plupart des cases de la grille sont blanches ou noires et où la case de la fourmi peut prendre huit états différents, codant à la fois sa couleur et la direction de la fourmi.

Propriétés

Attracteur

Fourmi de Langton sur une grille initialement vide après 11 000 étapes. En bas, on peut voir le début de la « route ». Le pixel rouge montre la position de la fourmi.

Ces règles simples conduisent à un comportement étonnant de la fourmi : après une période initiale apparemment chaotique, la fourmi finit par construire une « route » formée par 104 étapes qui se répètent indéfiniment. Il semble que cette route de 104 étapes soit un attracteur de la fourmi de Langton. Cet attracteur apparaît quand la grille est initialement vide et pour différentes conditions initiales. On conjecture que ce comportement reste vrai pour n'importe quel motif initial fini dessiné sur la grille (c'est par contre faux si on s'autorise un motif infini)[1].

Modèle de calcul

Certains problèmes sur la fourmi de Langton peuvent être reliés à l'évaluation d'un circuit booléen, un problème P-complet[2].

Extensions

Comportement de trois fourmis de Langton avec trois couleurs différentes.

Une extension simple consiste à utiliser plus de deux couleurs, modifiées de façon cyclique par la fourmi. Une dénomination simple de chaque fourmi consiste à assigner la lettre « G » ou « D » à chaque couleur afin d'indiquer si la fourmi doit tourner à gauche ou à droite lorsqu'elle la rencontre. Ainsi, la fourmi de Langton serait nommée « DG ».

Certaines de ces extensions produisent des motifs symétriques, comme « DGGD »[3].

Références

  1. ↑ (en) Christopher Langton, « Studing artificial life with cellular automata », Physica D, vol. 22, nos 1-3,‎ , p. 120-149 (DOI 10.1016/0167-2789(86)90237-X).
  2. ↑ (en) A. Gajardo, A. Moreira et E. Goles, « Complexity of Langton's ant », Discrete Applied Mathematics, vol. 117, nos 1-3,‎ , p. 41-50 (DOI 10.1016/S0166-218X(00)00334-6, lire en ligne).
  3. ↑ (en) David Gale, James Propp (en), Scott Sutherland et Serge Troubetzkoy, « Mathematical Entertainments: Further Travels with My Ant », The Mathematical Intelligencer, vol. 17, no 3,‎ , p. 48–56 (DOI 10.1007/BF03024370, arXiv math/9501233), réédité dans (en) Tracking the Automatic Ant, and Other Mathematical Explorations, New York, Springer, (ISBN 978-1-4612-7453-7), chap. 18, p. 137–149 (DOI 10.1007/978-1-4612-2192-0).

Voir aussi

Articles connexes

Liens externes

Sur les autres projets Wikimedia :

  • Fourmi de Langton, sur Wikimedia Commons
  • (en) Further Travels with my Ant par D. Gale, J. Propp, S. Sutherland et S. Troubetzkoy : article en format PostScript ou TeX détaillant une condition suffisante pour obtenir les motifs symétriques exprimés plus haut
  • (en) Langton's Ant Software, logiciel émulant la fourmi de Langton
  • (en) Applet java permettant de simuler des fourmis de différentes couleurs
  • (en) ASM32 app
  • icône décorative Portail de l'informatique théorique