Fourmi de Langton

La fourmi de Langton est la plus simple d’une famille de fourmis. Avec n couleurs, numérotées à partir de 0 pour le vide, une règle est une suite $r = r_0 r_1 \cdots r_{n-1}$ de lettres R et L, une par couleur. La fourmi de Langton correspond à RL. La fourmi se tient sur une case p, tournée dans une direction d, et un pas s’écrit

La fourmi n’a pas de mémoire et ne voit que la couleur sous ses pieds. Ici, vous pouvez la voir créer de l’ordre, puis un enchevêtrement, puis une route. Vous pouvez aussi la faire reculer, colorer des cases sur son chemin et essayer d’autres suites de lettres.

Les couleurs sont les états de la règle. Le plan n’a pas de bord et ne se reboucle pas sur lui-même. La courbe en haut du panneau compte les cases colorées après chaque pas.

Partant du plan vide, orientée vers le haut, la fourmi forme d’abord de petits motifs ordonnés, parfois symétriques par demi-tour, comme au pas 473. Suit un enchevêtrement d’apparence aléatoire pendant environ dix mille pas. Puis, à partir du pas 9 977, la fourmi répète les mêmes 104 mouvements, chaque cycle étant décalé de (−2, 2), soit deux cases à gauche et deux vers le bas. Elle construit une bande diagonale appelée autoroute, et chaque cycle de 104 pas ajoute exactement 12 cases colorées. Seuls les mouvements de la fourmi et la bande sous elle se répètent. L’enchevêtrement derrière reste en place.

Quelques cycles répétés ne prouvent rien : le suivant pourrait rencontrer une case colorée et dévier. La page ne garantit donc une route qu’après vérification. À la fin du dernier cycle, les cases lues, translatées du déplacement de la fourmi, doivent porter les couleurs que les cases d’origine avaient avant le cycle, et la fourmi doit retrouver sa direction initiale. De plus, dans chaque cycle futur, les cases situées au-delà de celles du cycle précédent doivent être vides maintenant et ne doivent avoir été visitées par aucun cycle depuis celui qui a été vérifié. Chaque cycle rencontre alors exactement ce que le précédent a rencontré et reproduit les mêmes mouvements, indéfiniment. La ligne pointillée sur la courbe marque le début de la répétition. Si une case colorée se trouve devant, la page l’entoure et ne donne aucune garantie.

Sur le plan vide, la route est donc prouvée par le calcul associé à cette vérification. Pour RL, tous les plateaux à nombre fini de cases colorées qui ont été essayés finissent par une route, mais personne n’a prouvé que c’est le cas de tous.

Chaque pas peut être annulé. La fourmi regarde dans la direction de son dernier déplacement : la case d’où elle vient est donc derrière elle, et la couleur de cette case a avancé d’un cran dans le cycle. Un pas en arrière s’écrit

Le plateau et la fourmi déterminent donc l’état un pas plus tôt. Arrière fait reculer la fourmi selon la règle, sans rejouer un enregistrement à l’envers.

Avec davantage de lettres, chaque visite fait passer une case à la couleur suivante. Depuis le plan vide, les boutons de règle font naître des formes très différentes : un motif d’apparence symétrique pour LLRR, un carré presque plein pour LRRRRRLLR, un triangle qui grandit pour RRLLLRLLLRRR. On ne sait pas comment ces trois cas évoluent à terme. LLRRRLRLRLLR construit bien une route, après environ trente mille pas.

Chris Langton a décrit la fourmi en 1986 comme exemple de vie artificielle.