La fourmi de Langton

Les élèves de la section d’excellence en mathématiques se sont intéressés durant plusieurs séances à la fourmi de Langton.

La fourmi de Langton est un petit programme informatique imaginé par un chercheur américain s’appelant Chris
Langton et 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… Voici les principes de base de la fourmi de Langton :
• une grille est couverte de cases blanches ou noires ;
• sur une des cases de la grille 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.

Les élèves ont donc programmé les déplacements de cette fourmi avec le logiciel Scratch.

Au début, les motifs dessinés par la fourmi sont symétriques à certaines étapes. Ensuite, les motifs dessinés sont entièrement chaotiques. Finalement, après plus de 10 000 étapes, un changement se produit : la fourmi se met à tracer un motif régulier, répété le long d’une diagonale que l’on appelle l’autoroute. Incroyable !

Au bout de 11 740 étapes :

Programme Scratch fourmi de Langton

Les élèves se sont ensuite intéressés au cas 3 couleurs. La règle DGD suivie par la fourmi est alors la suivante :

• couleur blanche touchée, je tourne à Droite et je colorie la case en orange ;
• couleur orange touchée, je tourne à Gauche et je colorie la case en bleue ;
• couleur bleue touchée, je tourne à Droite et je colorie la case en blanc.

La fourmi ne trace plus l’autoroute mais un motif aléatoire :

Programme Scratch fourmi de Langton 3 couleurs

Certains élèves ont alors rajouté davantage de couleurs et créé des règles de déplacement.

La fourmi de Langton 4 couleurs suivant la règle GDDG dessine une structure carrée avec des motifs complexes à l’intérieur :

Programme Scratch fourmi de Langton 4 couleurs

La fourmi de Langton 10 couleurs suivant la règle DGDDDDGGGD dessine une structure carrée plus simple :

Programme Scratch fourmi de Langton 10 couleurs

La fourmi de Langton 12 couleurs suivant la règle DDGGGDGGGDDD dessine une structure triangulaire :

Programme Scratch fourmi de Langton 12 couleurs