Home page de
Michel Casabianca

Actualité
oBlog
oNo Apple
oDebian sur Zotac Nano CI320
oDebian sur Acer C720P
oUn an avec un Raspberry Pi
oLes interfaces du GO
oParseurs YAML pour Go
oIntroduction à YAML
oNotes Formation Perl
oUtiliser le module Ruby MySQL
oUtiliser le module Ruby DBI
oScripts Python avec DB-API

Outils
oBabel
oBee
oTâches Ant
oInstalleur Java
oVisual SQL

MacOSX
oViewCVS sous MacOSX
oEmacs sous Panther

Conférences
oOutils J2EE Open Source
oDév. XML en Java sous Linux
oOutils de dév. Java sous Linux

Articles XML
oIntroduction à XML
oIntroduction à XSLT
oDéveloppement XML en Java
oGénérer des sites web avec Ant
oDTD Ant
oProject X

Articles Java
oTips CodeGuide
oKFM et Jars
oMails en Java
oJava et préprocesseur
oJava et images
oThreads
oÉvénements
oAstuces

Jeux
oAwele
oAtomX
oCore Warrior
oSolitaire
oSpiceWars
oTangram
oTaquin

Simulations
oJeu de la vie
oFourmi de Langton
oTri du couvain
oPiste de chasse

Graphisme
oFractales
oImages 3D
oPowered by ...
oEcce Duke
oTIE

À propos
oDe l'auteur
oDe ce site


Powered by

Powered by Debian
Règles | Applet

La fourmi de Langton - Règles

Michel CASABIANCA - casa@sweetohm.net

La fourmi de Langton

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.

Règles de déplacement et états

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".

Fourmi de Langton généralisée

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.

Conclusion

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...

Pour en savoir plus

  • Pour la science N°203 septembre 1994, page 94.

Règles | Applet


Dernière mise à jour :  2000-02-07