Fourmi de Langton

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

On nomme fourmi de Langton un automate cellulaire (voir machine de Turing) bidimensionnel comportant un jeu de règles très simples. On lui a donné le nom de Chris Langton, son inventeur.

Elle constitue l'un des systèmes les plus simples permettant de mettre en évidence un exemple de comportement émergent.

Règles[modifier | modifier le code]

Les cases d'une grille peuvent être blanches ou noires. On considère arbitrairement l'une de ces cases comme étant l'emplacement initial de la fourmi. Dans l'état initial, toutes les cases sont de la même couleur.

La fourmi peut se déplacer à gauche, à droite, en haut ou en bas d'une case à chaque fois selon les règles suivantes :

  • Si la fourmi est sur une case noire, elle tourne de 90° vers la droite, change la couleur de la case en blanc et avance d'une case.
  • Si la fourmi est sur une case blanche, elle tourne de 90° vers la gauche, change la couleur de la case en noir et avance d'une case.

Il est également possible de définir la fourmi de Langton comme un automate cellulaire où la plupart de la grille est blanche ou noire et où la case de la fourmi peut prendre huit états différents, codant à la fois sa couleur et la direction de la fourmi.

Propriétés[modifier | modifier le code]

Attracteur[modifier | modifier le code]

Comportement de trois fourmis de Langton avec trois couleurs différentes.

Ces règles simples conduisent à un comportement étonnant de la fourmi quand la grille est initialement vide: après une période initiale apparemment chaotique, la fourmi fini par construire une "route" formée par 104 étapes qui se répètent indéfiniment. On conjecture que ce comportement reste vrai pour n'importe quel motif initial fini dessiné sur la grille (c'est par contre faux si on s'autorise un motif infini). Il semble donc que cette route de 104 étapes soit un attracteur de la fourmi de Langton.

Modèle de calcul[modifier | modifier le code]

Certains problèmes sur la fourmi de Langton peuvent être relié à l'évaluation d'un circuit booléen, un problème P-complet[1].

Extensions[modifier | modifier le code]

Une extension simple consiste à utiliser plus de deux couleurs, modifiées de façon cyclique par la fourmi. Une dénomination simple de chaque fourmi consiste à assigner la lettre « G » ou « D » à chaque couleur afin d'indiquer si la fourmi doit tourner à gauche ou à droite lorsqu'elle la rencontre. Ainsi, la fourmi de Langton serait nommée « DG ».

Certaines de ces extensions produisent des motifs symétriques, comme par exemple « DGGD ».

Références[modifier | modifier le code]

  1. A. Gajardo, A. Moreira et E. Goles, « Complexity of Langton's ant », Discrete Applied Mathematics, vol. 117, no 1-3,‎ 2002, p. 41-50 (DOI 10.1016/S0166-218X(00)00334-6, lire en ligne)

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Sur les autres projets Wikimedia :