La fourmi de Langton est un petit programme informatique qui décrit une fourmi se déplaçant sur les cases d’une grille. Les règles qui régissent le mouvement de la fourmi sont d’une grande simplicité, et pourtant son comportement est complexe et tout sauf anodin.
Et personne ne comprend vraiment pourquoi…
Les règles du jeu
Pour jouer à la fourmi de Langton (du nom de son créateur Chris Langton) il vous faut une feuille quadrillée, un crayon et une gomme. Au départ les cases de la grille peuvent être blanches ou noires, mais supposons pour commencer qu’elles sont toutes blanches. Mettez une petite flèche dans une des cases : ce sera votre fourmi, et l’orientation de la flèche indiquera sa direction.
A chaque tour, la fourmi se déplace selon les règles suivantes :
- Si la fourmi est sur une case blanche, elle effectue une rotation vers la gauche; si elle est sur une case noire, elle effectue une rotation vers la droite ;
- La fourmi inverse la couleur de la case sur laquelle elle se trouve (blanc devient noir et réciproquement);
- La fourmi avance d’une case dans la direction de son orientation.
Les phases de la vie de la fourmi
A vue de nez, rien de bien enthousiasmant dans cette fourmi. Elle obéit à des règles très simples et on se dit que son évolution ne va pas être bien passionnante. Et pourtant, quand on la simule pendant quelques milliers de tours, il se passe des choses vraiment étonnantes.
En effet, la fourmi va passer par 3 phases vraiment très différentes, la phase « symétrique », la phase « chaotique » et la phase « autoroute ».
Au début de son évolution, la fourmi se balade dans une zone assez limitée de la grille, en dessinant desconfigurations régulières et symétriques. En voici quelques exemples (la fourmi est en rouge) :
Quand on voit ces figures, on peut penser que la fourmi de Langton va passer le restant de son existence à dessiner des jolies choses bien symétriques. Mais à partir de 500 tours, tout change. Elle se met à avoir un comportement chaotique, en élargissant son terrain de jeu et en créant des configurations très irrégulières.
Cette phase chaotique dure jusqu’à environ 10000 tours, et là le miracle se produit : la fourmi entame la construction d’une autoroute très régulière qui la conduit à l’infini.
Le mystère de l’autoroute
L’autoroute est en fait un motif périodique de 104 pas qui se répète, et conduit au tracé que vous observez sur le film précédent. Personne ne comprend pourquoi elle apparaît et comment elle peut émerger du désordre qui caractérise la phase chaotique.
Ce qu’il y a de plus perturbant, c’est que même si on part d’une grille dont les cases sont coloriées aléatoirement en blanc ou en noir, l’autoroute finit toujours par apparaître un jour ou l’autre.
C’est encore un problème ouvert de démontrer que quelle que soit la configuration initiale, une autoroute apparaît (à moins de chercher un contre-exemple, mais aucun n’a été trouvé à ce jour).
Toutefois un pas intéressant a été franchi : on peut démontrer que la trajectoire de la fourmi est toujours non-bornée. C’est à dire que la fourmi finit toujours son parcours à l’infini…mais on ne sait pas montrer que c’est toujours via une construction d’autoroute !
