L'applet présentée dans cette page permet de visualiser le
parcours de la fourmi de Langton généralisée. La fourmi de Langton
est une sorte d' automate cellulaire (comme le jeu de la vie)
d'une grande simplicité: une fourmi se déplace sur un plateau
quadrillé initialement rempli de cases blanches. La fourmi se
déplace chaque tour d'une case. Si elle tombe sur une case
blanche, elle la peint en noir et tourne à droite. Si la case est
noire, elle la peint en blanc et tourne à gauche. Elle répète
ainsi ses déplacements jusqu'à ce qu'elle sorte du plateau.
On peut donc dire que les cases du plateau peuvent prendre 2
états : blanc (0) ou noir (1). La règle de déplacement peut alors
être codée dans une chaine de deux caractères : DG. Cette chaine
veut dire que si la case où arrive la fourmi est dans l'état 0, la
fourmi tourne à droite (D) et peint la case dans l'état suivant,
soit 1 (noir). Le caractère suivant (G) veut dire que si la fourmi
arrive sur une case noire (état 1), elle tourne à gauche (G) et
peint la case en blanc (0), état suivant si on considère que la
chaine des règles "se mord la queue".
On peut généraliser la fourmi da Langton : les cases du plateau
peuvent prendre N états. La règle de déplacement de la fourmi peut
alors se coder sur une chaine de N caractères. Si la fourmi arrive
sur une case à l'état k, alors la case passe à l'état k+1 et la
fourmi change de direction de déplacement en tournant à droite (si
la chaine contient D en position k) ou à gauche (si la chaine
contient G en position k).
La fourmi de Langton n'est plus alors qu'un cas particulier de
la fourmi de Langton généralisée (pour laquelle le nombre d'états
est de 2, et la chaine des règles est DG). Les réglages par défaut
de l'applet traitent ce cas particulier de la fourmi de
Langton.
La fourmi de Langton est intéressante pour plusieurs raisons
:
Elle montre que des règles simples (celles des déplacements de
la fourmi sont on ne peut plus simples !) peuvent conduire à un
comportement chaotique : lors des 10 000 premiers pas, les
déplacements de la fourmi semblent totalement désordonnés. Cette
simple constatation permet de comprendre que des lois physiques
simples qui s'appliquent à des objets simples (comme les atomes)
conduisent à des comportements imprévisibles, même si ces lois
sont parfaitement connues. Certaines fourmis généralisées semblent
ainsi avoir un comportement indéfiniment chaotique; c'est le cas
de la DGG qui ne forme aucun motif régulier jusqu'au 150 000 000
ème coup au moins (le contraire reste à prouver).
Cependant, si on laisse évoluer le système suffisament
longtemps (environ 11 000 coups), on constate que le comportement
de la fourmi DG change totalement pour devenir parfaitement
ordonné : elle part "en ligne droite" avec un cycle de 104
coups. Du comportement chaotique de la fourmi émerge une
organisation ! Mais n'en est-il pas de même pour les fourmis (les
vraies, celles qui cavalent dans votre jardin, celles que vous
écrasiez quand vous étiez petit) ? Prises individuellement, elles
ont un comportement simple (il ne pourrait en être autrement vu la
taille de leur cerveau), mais quand on les observe, elles cavalent
en tous sens et on a du mal à comprendre la finalité de leurs
déplacements, pourtant, la fourmilière est entretenue, les oeufs
sont choyés et les fourmis prospèrent...
Bref, je pourrais en parler des heures, mais le mieux est de
tester par soi même. Quel plaisir de voir cette petite fourmi
cavaler frénétiquement dans tous les sens, en se demandant si elle
va errer indéfiniment...
