Boucle de Langton

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.

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.

• 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 0-19-875155-9)