Exploration de la fourmi de Langton

La fourmi de Langton : quelques règles simples pour tracer un chemin inattendu

Si vous placez une fourmi sur une feuille de papier recouverte d'une grille en noir et blanc et que vous lui donnez seulement deux instructions simples — tourner à droite sur une case blanche, et tourner à gauche sur une case noire — puis que vous la laissez continuer son chemin, que pensez-vous qu'il finira par se produire ? Peut-être un enchevêtrement chaotique de lignes, ou peut-être la fourmi fera-t-elle simplement des allers-retours au même endroit — ou peut-être ne se passera-t-il rien de particulier.

Mais ce qui est vraiment surprenant, c'est qu'après un certain temps, la fourmi finit par « trouver un chemin » et se met à avancer régulièrement vers l'extérieur, en suivant une ligne diagonale bien nette.

C'est ce qu'on appelle la célèbre fourmi de Langton.

Il n'y a ici ni formules complexes, ni nombres aléatoires, ni même beaucoup de règles. Il s'agit simplement d'une fourmi, d'une grille en noir et blanc et de quelques instructions très élémentaires.

Pourtant, lorsque ces règles simples sont appliquées sur une longue durée, elles donnent naissance à un comportement d'une complexité inattendue.

Les règles de la fourmi de Langton

Ne compliquons pas les choses ; commençons par le scénario le plus simple.

Imaginez une grille composée de nombreux petits carrés — tous blancs au départ — sur laquelle se trouve une fourmi. Donnons maintenant quelques instructions à cette fourmi.

□ □ □ □ □

□ □ □ □ □

□ □ 🐜 □ □

□ □ □ □ □

□ □ □ □ □

Les règles sont très simples.

Si la fourmi se trouve sur un carré blanc, elle tourne vers la droite, change la couleur du carré en noir, puis avance d'un pas vers le carré suivant.

Si la fourmi se trouve sur un carré noir, elle tourne vers la gauche, change la couleur du carré en blanc, puis avance d'un pas vers le carré suivant.

Voilà, c'est tout — aussi simple que cela, sans aucune autre règle. La fourmi ne se dit pas : « Je vais créer un joli motif », elle ne prévoit pas de « se diriger vers le haut à droite » et ne se demande pas non plus « jusqu'où elle doit aller ». Elle se contente d'observer la couleur → tourner → changer la couleur → avancer. Ensuite, elle répète le processus, encore et encore.

Au début, cela semble tout à fait ordinaire

Lors des premiers pas, la fourmi se contente d'errer dans son voisinage immédiat. Elle passe sur une case blanche, tourne à droite et la transforme en case noire. Lorsqu'elle repasse par là plus tard et rencontre une case noire, elle tourne à gauche et la transforme à nouveau en case blanche. Ainsi, la fourmi se déplace de long en large dans la zone.

Si vous ne la laissez fonctionner que pendant quelques dizaines de pas, vous pourriez vous dire : « Eh bien, il n'y a rien de bien particulier ici. » Mais ne vous arrêtez pas tout de suite.

Continuez à la laisser fonctionner.

Après 100 pas, les cases blanches et noires commencent à s'entremêler. De petits blocs apparaissent par endroits, tandis que des motifs symétriques se forment ailleurs. L'ensemble commence à gagner en complexité.

Continuez.

Après 1 000 pas, la fourmi a parcouru une zone beaucoup plus vaste. Le motif en noir et blanc qu'elle laisse derrière elle ne ressemble plus à une simple forme géométrique. Il devient pratiquement impossible de prédire où la fourmi se déplacera ensuite. Tout semble totalement chaotique.

Alors continuez

Des règles simples ne garantissent pas des résultats simples

Pourtant, au départ, le phénomène ne ressemble en rien à ce qu'il finit par devenir — et c'est précisément ce qui rend la « fourmi de Langton » si fascinante.

Si l'on n'observe que les quelques premières douzaines d'étapes, on pourrait conclure : « La fourmi erre sans but précis. » Même après quelques centaines d'étapes, le comportement semble toujours chaotique. Pendant une longue période, il est pratiquement impossible de deviner quel type de motif finira par émerger.

Et pourtant, les règles elles-mêmes restent immuables ; ce qui change, c'est que ces règles sont appliquées, encore et encore.

L'enseignement le plus profond que nous offre la fourmi de Langton est le suivant : un système peut être régi par des règles très simples, tout en produisant un comportement à long terme d'une grande complexité.

Nous supposons souvent, de manière intuitive, qu'un système régi par un petit nombre de règles ne devrait pas aboutir à un résultat particulièrement complexe. La fourmi de Langton nous montre pourtant qu'il n'en est rien.

À mesure qu'une règle simple est appliquée de façon répétée aux résultats de ses propres actions précédentes, le système engendre des états de plus en plus complexes — des états qui, à leur tour, déterminent la suite des événements.

En résumé : Simple → Complexe → Encore plus complexe → Émergence de nouvelles structures.

Les fourmis ne possèdent pas réellement de « mémoire »

Un autre point particulièrement intéressant est qu'une fourmi n'a pas besoin de se demander : « Où suis-je allée ? ». Elle a seulement besoin d'observer : « Quelle est la couleur du sol sous mes pieds en ce moment même ? »

Pourtant, le système dans son ensemble possède une forme de « mémoire ».

Pourquoi ? Parce que la fourmi modifie les cases de la grille qu'elle traverse.

Par conséquent, les événements passés sont inscrits dans la grille en noir et blanc ; lors de son prochain passage, la fourmi y découvre une couleur différente.

Ainsi, les actions passées remodèlent l'environnement actuel, et cet environnement, à son tour, influence les actions futures.

Cela crée un cycle remarquable : la fourmi modifie la grille → la grille influence le déplacement suivant de la fourmi → la fourmi modifie à nouveau la grille → la grille influence encore la fourmi → et ainsi de suite.

En observant les « autoroutes » qui finissent par apparaître, on pourrait facilement croire, à tort, que « la fourmi sait forcément où elle va ».

Bien entendu, ce n'est pas le cas. Elle n'a ni objectif, ni carte, ni système de navigation, ni itinéraire prédéfini. Elle se contente d'appliquer une règle mécanique : tourner à droite sur une case blanche, tourner à gauche sur une case noire.

Pourtant, des comportements complexes émergent spontanément de ces règles simples.

C'est ce que l'on appelle : l'émergence.

Alors, pourquoi les fourmis finissent-elles par s'éloigner ?

C'est un autre aspect fascinant de la « fourmi de Langton ».

Une fois qu'une « autoroute » s'est formée — à condition que le nombre total de pas soit suffisamment élevé — la fourmi continue de parcourir ce chemin, sans jamais revenir en arrière. À terme, la fourmi peut même finir par sortir de l'écran.

Il ne s'agit pas d'une erreur de programmation, et cela ne signifie pas non plus que le système est devenu « incontrôlable ». En réalité, la fourmi a simplement trouvé sa propre autoroute ; elle continue de suivre les règles initiales, poursuivant son périple toujours plus loin, vers l'inconnu.

Une fourmi, un échiquier et quelques règles

Ne vous focalisez donc pas uniquement sur le motif final. Ce qui mérite vraiment d’être observé dans la « fourmi de Langton », c’est le processus dans son ensemble : chaos → complexité → évolution à long terme → apparition soudaine d’un ordre → une « autoroute » → une expansion continue vers l’extérieur.

Cela diffère de bon nombre de modèles mathématiques que nous rencontrons habituellement. Il ne s’agit pas de dire : « Voici une réponse belle et définitive », mais plutôt : « Voyons comment ce système évolue par lui-même. »

Dans beaucoup de modèles mathématiques, tout l’intérêt réside dans les paramètres : modifiez-les, et vous obtenez un univers totalement nouveau.

Avec la fourmi de Langton, en revanche, la surprise naît du temps ; il suffit d’appuyer sur « démarrer » et d’attendre.

Impossible de savoir ce qui se produira à la 10e, à la 1 000e ou à la 10 000e étape. En fin de compte, une règle si simple qu’elle en devient presque un jeu peut vous mener sur un chemin qui n’avait jamais été tracé à l’avance.

L’aspect peut-être le plus fascinant de la fourmi de Langton se résume en une seule phrase : elle ne sait pas où elle va, et pourtant, elle finit par se frayer un chemin.

Personne n’a fourni de carte, personne n’a fixé de destination, et personne n’a conçu d’« autoroute ». Il n’y a que ceci : blanc → tourner à droite ; noir → tourner à gauche ; inverser la couleur ; faire un pas en avant — et recommencer, encore et encore.

En quoi la fourmi de Langton diffère-t-elle des fractales ?

Bien que la fourmi de Langton puisse apparaître comme une forme d'art mathématique générant continuellement des motifs, elle se distingue des fractales telles que l'ensemble de Mandelbrot ou le flocon de neige de Koch.

Par exemple, le flocon de neige de Koch est régi par des règles qui modifient une forme de manière récursive, la structure de l'itération suivante étant prédéterminée.

L'ensemble de Mandelbrot est défini par l'itération répétée d'une équation impliquant des nombres complexes, où différents points de départ conduisent à des trajectoires différentes.

À l'inverse, la fourmi de Langton met en scène un « agent » qui agit au sein de son environnement et le modifie. Son déplacement suivant dépend non seulement de sa position actuelle, mais aussi des traces qu'elle a laissées derrière elle. Ainsi, ce que l'on observe n'est pas simplement une récursion géométrique, mais un système caractérisé par une interaction continue entre un agent et son environnement.

Quelle est la différence entre la fourmi de Langton et l'attracteur Hopalong ?

Bien que la fourmi de Langton et l'attracteur Hopalong présentent certaines similitudes, ils incarnent chacun une forme unique et fascinante d'« imprévisibilité ».

Attracteur Hopalong : De magnifiques motifs se cachent souvent au sein de l'espace des paramètres ; une infime modification de ces paramètres peut aboutir à un résultat totalement différent. On ne sait jamais ce que l'on peut découvrir en changeant un paramètre : ici, l'effet de surprise naît de l'espace des paramètres.

Fourmi de Langton : Les règles de base sont fixes, mais à mesure que le nombre d'itérations augmente, la fourmi finit par « s'échapper » de sa zone initiale restreinte. Par ailleurs, les motifs locaux qui apparaissent au début diffèrent radicalement des comportements observés par la suite. Il est impossible de prédire ce qui se produira après qu'un ensemble simple de règles a été appliqué pendant une durée suffisamment longue : ici, l'effet de surprise naît du temps et du nombre d'itérations.

Continuez à explorer le monde des mathématiques

Vous pouvez continuer à explorer d'autres modèles mathématiques fascinants, ou consulter plus d'informations sur la fourmi de Langton sur Wikipédia.