Boucle de Langton

Boucle de Langton

La boucle de Langton est une structure autoréplicante d'un automate cellulaire créée par Christopher Langton (en) en 1984[1].

Sommaire

Histoire

Les automates cellulaires tirent leur origine avec la volonté de John von Neumann de créer un système capable de se dupliquer lui-même. En 1947, von Neumann créa son constructeur universel, automate complexe à 29 états, mais répondant au problème. En 1968, Edgar F. Codd le simplifia avec seulement 8 états en créant l'automate qui porte son nom.

Ces automates cellulaires possédaient donc la propriété d'autoréplication, mais elle découlait d'une propriété d'universalité et conduisait à des règles et des structures lourdes.

Au début des années 1980, Christopher Langton considéra le problème dans l'autre sens. Il conçut un automate cellulaire bâti autour d'une structure qui contenait en elle-même l'information permettant sa réplication. La "boucle de Langton" ainsi créée ne contient que les éléments nécessaires à sa copie (à l'instar de l'ADN) : elle n'est donc pas universelle, mais considérablement plus simple que les constructeurs précédents.

Description

L'automate utilisé par Langton est bidimensionnel. Chaque cellule peut prendre 8 états différents et possède 4 voisines (à gauche, à droite, en haut, en bas). Il existe 29 règles de transition permettant de déterminer l'état suivant d'une cellule à partir de son état présent.

La boucle de Langton est formée par un filament de cellules à l'état 1 formant une boucle, entouré par une membrane de cellules à l'état 2. Sur ce filament sont à l'origine placés une succession de signaux, composés d'une cellule à l'état 4, 5, 6 ou 7 suivie d'une cellule à l'état 0, qui forment en quelque sorte le code génétique de la boucle. Cette dernière est terminée par une excroissance par laquelle s'effectuera la réplication.

La structure initiale de 86 cellules est la suivante :

  2 2 2 2 2 2 2 2
2 1 7 0 1 4 0 1 4 2
2 0 2 2 2 2 2 2 0 2
2 7 2         2 1 2
2 1 2         2 1 2
2 0 2         2 1 2
2 7 2         2 1 2
2 1 2 2 2 2 2 2 1 2 2 2 2 2
2 0 7 1 0 7 1 0 7 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2

Chaque signal se propage dans un sens le long du filament. Lorsqu'ils arrivent au niveau de la jonction entre le filament et l'excroissance, ils sont dupliqués : une copie se propage dans l'excroissance tandis qu'une autre continue dans le filament.

Lorsqu'un signal arrive en bout de bras, il cesse de se propager et réalise une instruction particulière (agrandissement de l'excroissance, création d'un coude dans celle-ci, etc.). Cela conduit à la création d'une deuxième boucle le long de l'excroissance. Lorsque cette boucle est terminée, un dernier signal la sépare définitivement de la boucle initiale : la réplication est alors complète et l'automate possède désormais deux boucles aptes à se dupliquer.

Chaque boucle possède enfin une règle de stérilisation permettant d'arrêter la duplication d'une boucle après plusieurs réplications.

Notes et références

  1. Christopher G. Langton, Self-reproduction in cellular automata, Physica D n° 10 (1984), pp 135-144

Bibliographie

  • Christopher G. Langton, Studying Artificial Life with cellular automata, Physica D n° 22 (1986)
  • Christopher G. Langton, Artificial Life in The philosophy of Artificial Life, Oxford readings in Philosophy, Oxford University Press (1996), pp. 64 et suivantes - ISBN 0198751559

Annexes

Liens internes


Liens externes


Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Boucle De Langton — La boucle de Langton est une structure autoréplicante d un automate cellulaire créée par Christopher Langton en 1984[1]. Sommaire 1 Histoire 2 Description 3 Notes et référenc …   Wikipédia en Français

  • Boucle de langton — La boucle de Langton est une structure autoréplicante d un automate cellulaire créée par Christopher Langton en 1984[1]. Sommaire 1 Histoire 2 Description 3 Notes et référenc …   Wikipédia en Français

  • Boucle De Byl — La boucle de Byl est une structure autoréplicante d un automate cellulaire particulier[1]. L automate cellulaire comporte 6 états distincts, tandis que la structure originale de la boucle est composée de 12 cellules : 22 2312 2342 25 Le… …   Wikipédia en Français

  • Boucle de byl — La boucle de Byl est une structure autoréplicante d un automate cellulaire particulier[1]. L automate cellulaire comporte 6 états distincts, tandis que la structure originale de la boucle est composée de 12 cellules : 22 2312 2342 25 Le… …   Wikipédia en Français

  • Boucle SDSR — La boucle SDSR est une structure autoréplicante d un automate cellulaire particulier, introduit par Hiroki Sayama en 1998[1] Le terme SDSR est un acronyme signifiant Structurally Dissolvable Self Reproducing (autoréplicante structurellement… …   Wikipédia en Français

  • Boucle de Byl — La boucle de Byl est une structure autoréplicante d un automate cellulaire particulier[1]. L automate cellulaire comporte 6 états distincts, tandis que la structure originale de la boucle est composée de 12 cellules : 22 2312 2342 25 Le… …   Wikipédia en Français

  • Boucle de rétroaction — Rétroaction Représentation d une boucle rétroactive. La rétroaction (on utilise aussi couramment le terme anglais feedback), est, au sens large, l’action en retour d’un effet sur le dispositif qui lui a donné naissance, et donc, ainsi, sur elle… …   Wikipédia en Français

  • Boucles de Chou-Reggia — Les boucles de Chou Reggia sont deux structures autoréplicantes d un automate cellulaire particulier à 8 états[1]. La première boucle est composée de 6 cellules : 11 3411 La deuxième boucle n est composée que de 5 cellules : 11 341 Le… …   Wikipédia en Français

  • Evoloop — Évolution d evoloops. Différentes espèces sont présentes mais les plus petites tendent à occuper tout l espace L evoloop (littéralement « boucle évolutive ») est une structure autoréplicante d un automate cellulaire particulier à 9… …   Wikipédia en Français

  • Boucles De Chou-Reggia — Les boucles de Chou Reggia sont deux structures autoréplicantes d un automate cellulaire particulier à 8 états[1]. La première boucle est composée de 6 cellules : 11 3411 La deuxième boucle n est composée que de 5 cellules : 11 341 Le… …   Wikipédia en Français

Share the article and excerpts

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