Fourmi De Langton

Fourmi De Langton

Fourmi de Langton

On nomme fourmi de Langton un automate cellulaire (voir : machine de Turing) bidimensionel comportant un jeu de règles très simples. Elle fut inventée par Chris Langton dont on lui a donné le nom.

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

Sommaire

Règles

Les cases d'une grille peuvent être blanches ou noires. On considère arbitrairement l'une de ces cases comme étant 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

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

Ces règles simples conduisent à un comportement étonnant de la fourmi : après une période initiale apparemment chaotique, la fourmi finit invariablement par construire une route formée par 104 étapes qui se répètent indéfiniment, quel que soit le motif initial. Il semble que cette route soit un attracteur de la fourmi de Langton.

Extensions

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

Voir aussi

Liens internes

Liens externes

Commons-logo.svg

  • Portail des mathématiques Portail des mathématiques
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Fourmi de Langton ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fourmi De Langton de Wikipédia en français (auteurs)

Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Fourmi de langton — On nomme fourmi de Langton un automate cellulaire (voir : machine de Turing) bidimensionel comportant un jeu de règles très simples. Elle fut inventée par Chris Langton dont on lui a donné le nom. Elle constitue l un des systèmes les plus… …   Wikipédia en Français

  • Fourmi de Langton — 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… …   Wikipédia en Français

  • Fourmi (Homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Cet article possède des paronymes, voir : Fourmies et FourmiZ …   Wikipédia en Français

  • Fourmi — Formicidae Pour les articles homonymes, voir fourmi (homonymie) …   Wikipédia en Français

  • Fourmi (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Cet article possède des paronymes, voir : Fourmies et FourmiZ. Sur les autres …   Wikipédia en Français

  • La fourmi — Formicidae Pour les articles homonymes, voir fourmi (homonymie) …   Wikipédia en Français

  • Formicidae — Pour les articles homonymes, voir fourmi (homonymie). Fourmis …   Wikipédia en Français

  • Colonies de fourmis — Formicidae Pour les articles homonymes, voir fourmi (homonymie) …   Wikipédia en Français

  • Formicidea — Formicidae Pour les articles homonymes, voir fourmi (homonymie) …   Wikipédia en Français

  • Formicidé — Formicidae Pour les articles homonymes, voir fourmi (homonymie) …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”