La Fourmi de Langton

Principes

Voici les principes de base de la fourmi de Langton :

• L'univers est une surface plane, couverte de cases carrées.
• Chaque case affiche une couleur : soit blanche, soit noire. Initialement, toutes les cases sont blanches.
• Sur une des cases se trouve une fourmi, capable de tourner, d'avancer et de changer la couleur de sa case.

Les actions de la fourmi sont déterminées par la couleur de la case sur laquelle elle se trouve, et se déroulent toujours dans le même ordre :

• Si sa case est blanche : la fourmi tourne d'un quart de tour vers la droite, change la couleur de sa case en noir, et avance d'une case.
• Si sa case est noire : la fourmi tourne d'un quart de tour vers la gauche, change la couleur de sa case en blanc, et avance d'une case.

L'animation interactive ci-dessous (compatible avec Firefox et Chromium) permet de visualiser pas à pas le comportement de la fourmi pour mieux comprendre, durant les dix premières étapes de son itinéraire, en cliquant sur les boutons correspondant à ses actions.

Cette animation interactive requiert un élément canvas qui ne fonctionne pas dans ce navigateur.

Recommencer

1. Créer le terrain
2. Placer la fourmi
3. Répéter :
   1. Tourner
   2. Colorer
   3. Avancer

Comportement

En observant les premiers mouvements de la fourmi, en particulier jusqu'à l'étape 8, on remarque une certaine symétrie dans ses déplacements, qui la ramène sur la case centrale.

Pour autant, la fourmi ne tourne pas en rond car, si elle repasse sur sa case initiale, l'environnement autour d'elle a changé : certaines cases sont devenues noires, ce qui la conduit à adopter par la suite une trajectoire différente, plus large, et finalement à sortir du terrain exigu où nous l'avions placée.

Mais si le terrain n'est pas borné, qu'advient-il de la fourmi ? Va-t-elle effectuer une série d'actions cycliques, et reproduire sans cesse le même motif ? Si oui, au bout de combien de temps ? Va-t-elle aller toujours plus loin, explorant à l'infini de nouvelles cases du terrain ?

Trouver une réponse à ces questions est étonamment peu intuitif, et en donner la preuve plus difficile encore. Avant de se prononcer, peut-être faudrait-il en voir davantage. Nous avons pu observer les dix premières étapes. Que se passe-t-il après cent étapes ? Après mille ? Après dix mille ?

Un bon informaticien est un informaticien fainéant., dit-on parfois en plaisantant, car le meilleur informaticien n'est pas celui qui fait, mais celui qui fait faire à la machine. Alors en bons informaticiens, laissons l'ordinateur calculer ce qu'il advient de la fourmi, et observons ses déplacements.

L'animation interactive ci-dessous (compatible avec Firefox et Chromium) permet de simuler, pas à pas ou en accéléré, les déplacements de la fourmi (désormais représentée par un triangle rouge), ansi que d'ajuster la vitesse de la simulation. Elle fonctionne jusqu'à sa sortie du terrain, après un peu plus de 11 000 étapes. Observez les déplacements de la fourmi. Quelles sont vos conclusions ?

Observations

À l'étude des tracés effectués par la fourmi, certaines étapes (8, 96, 184, 368, 472) semblent particulièrement remarquables, par la symétrie des motifs qu'elles présentent. À l'inverse, d'autres passages (entre 500 et 10 000) ne semblent pas exhiber de structure particulière, et les motifs correspondants sont entièrement chaotiques. Finalement, après environ 10 200 étapes, un changement se produit : la fourmi cesse ses déplacements erratiques, et se met à tracer un motif régulier, répété le long d'une diagonale.

Ce motif tracé par la fourmi de Langton est surnomé l'autoroute. Tout porte à croire qu'une fois entamée, cette autoroute se poursuit indéfiniment, et c'est en effet le cas. Agrandir le terrain pour poursuivre la simulation est sans intérêt : l'autoroute s'étend simplement plus loin, deux cases à gauche et deux cases plus bas, selon un cycle de 104 étapes.

C'est ici que s'achève le travail de la machine, et que la réflexion reprend ses droits. Pourquoi ce motif en particulier ? Si les conditions initiales avaient été différents (par exemple, en noircissant certaines cases sur le trajet de la fourmi), en serait-il allé autrement ? Existe-t-il d'autres motifs capables, comme l'autoroute, de piéger la fourmi de Langton ?

Raisonnement

Un résultat mathématique essentiel est démontré pour la fourmi de Langton : sa trajectoire n'est pas bornée, c'est-à-dire que la fourmi visite toujours tôt ou tard de nouvelles cases. En d'autres termes, il n'est pas possible de délimiter une région finie dont la fourmi ne sortira jamais.

Ce résultat semble évident après avoir observé le tracé de l'autoroute, mais il y a une différence importante en mathématique et en informatique entre une conjecture (une hypothèse qui semble juste, fondée sur l'observation) et un théorème (une certitude, justifiée par un raisonnement rigoureux).

De plus, le raisonnement qui soutient ce théorème est valable pour toute configuration de départ : aucune combinaison de cases noires ou blanches ne peut empêcher la fourmi de poursuivre sa route indéfiniment, ce qui serait difficile à vérifer à l'aide d'une machine (après tout, il existe une infinité de configurations initiales).

La preuve du théorème elle même n'est pas très complexe, et assez simple à suivre pour un mathématicien (voir en bas de cette page pour les curieux) ; cependant, si elle permet de se convaincre que la trajectoire de la fourmi n'est pas bornée, elle ne décrit pas exactement la nature de cette trajectoire : l'autoroute que nous avons pu observer ne figure nulle part dans cette démonstration.

D'autres expériences ont été conduites avec la fourmi de Langton, pour observer son comportement avec différentes configurations initiales. Si son comportement varie en fonction des cases noires placées sur son chemin, toutes les expériences semblent suggérer qu'une autoroute finit par se former et se poursuivre indéfiniment, pour toute configuration initiale finie (c'est-à-dire qui comporte un nombre donné de cases noires ou blanches). Mais cette fois, il ne s'agit que d'une conjecture : il n'existe pas de preuve que l'autoroute soit la seule configuration que la fourmi poursuive indéfiniment.

Il existe d'autres variantes de la fourmi de Langton : certaines incluent plusieurs fourmis, d'autres permettent davantage de couleurs (et donc d'instructions) différentes, et enfin certaines attribuent à la fourmi (qu'on appelle alors une turmite) un état interne, qui influe également sur son comportement et change en fonction de la couleur des cases rencontrées. Mais ceci est une autre histoire...

Annexes

Références

Voici quelques autres ressources qui parlent de la fourmi de Langton :

• Christopher Langton, "Studying Artificial Life with Cellular Automata" (l'article original de Christopher Langton)
• L'article et la vidéo de David Louapre, alias Science Étonnante
• Jean-Paul Delahaye, "Les Intrigants Chemins de la fourmi de Langton" (Pour la science N°503)
• La Fourmi de Langton sur Wikipédia (et sa version anglophone, plus complète)
• Terry Pratchett, Ian Stewart et Jack Cohen, "La Science du Disque-Monde"
• La Colonie de Langton

En outre, une autre expérience d'informatique (la Colonie de Langton) est désormais disponible, pour expérimenter avec des variantes plus riches (et plus colorées !) de la fourmi présentée dans cet article.

Preuve du théorème

La trajectoire de la fourmi de Langton n'est pas bornée. Ce théorème peut se déduire de résultats connus sur la trajectoire des particules dans les simulations de gaz à base d'automates cellulaires, attribués selon les sources à Kong et Cohen ("Diffusion and Propagation in Triangular Lorentz Lattice Gas Cellular Automata", 1991) ou Bunimovich et Troubetzkoy ("Recurrence Properties of Lorentz Lattice Gas Cellular Automata", 1992).

Dans le cas de la fourmi de Langton, le raisonnement peut être formulé comme suit :

1. Tout d'abord, en raison des règles qui la font tourner d'un quart de tour, si la fourmi arrive sur une case dans l'axe vertical, elle en sort en entrant sur une case adjacente dans l'axe horizontal, et réciproquement. Par conséquent, les cases du terrain forment un damier où, sur chaque ligne et chaque colonne, une case sur deux est une case dite horizontale (la fourmi y entre toujours depuis l'est ou l'ouest), et l'autre une case verticale (la fourmi arrive toujours du nord ou du sud).
2. Supposons maintenant que la trajectoire de la fourmi est bornée : comme la fourmi ne visite alors qu'un nombre fini de cases alors qu'elle circule indéfiniment, il s'ensuit qu'un ensemble de cases sera visité indéfiniment.
3. Parmi celles-ci il en existe au moins une qui forme un "coin", c'est-à-dire telle que les cases situées à l'est et au nord de celle-ci ne sont pas visitées indéfiniment (sinon la trajectoire ne serait pas bornée). Deux cas de figure sont alors possibles, d'après le lemme 1 :
   1. Soit le coin est une cellule horizontale, visitée indéfiniment : la fourmi doit donc y entrer indéfiniment par l'ouest, et comme la couleur de la case change à chaque visite, en sortir indéfiniment vers le sud et vers le nord (une fois sur deux), ce qui est une contradiction.
   2. Soit le coin est une cellule verticale, visitée indéfiniment : la fourmi doit donc y entrer indéfiniment par le sud, et selon le même raisonnement, elle en ressort aussi souvent vers l'ouest que vers l'est, également une contradiction.
4. Tous les cas mènent à une contradiction, donc l'hypothèse 2 est absurde. La trajectoire de la fourmi n'est donc pas bornée, CQFD.