Tech

Auto-reproduction des automates cellulaires

Dossier - Les automates cellulaires
DossierClassé sous :robotique , automates cellulaires , automate cellulaire

Jérôme Damelincourt

-

Développement assez récent de la science initié par les travaux de Von Neumann , et mis à portée d'un public plus large par des réalisations comme le Jeu de la Vie de Conway, les automates cellulaires, jouent leur atout en ingénierie et dans la recherche.

  
DossiersLes automates cellulaires
 

Les informations recueillies sur cette page sont tirées de l'excellente page web de Moshe Sipper : The Artificial Self-Replication Page.

Qu'est-ce que l'auto-reproduction ?

John Von Neumann a été le premier dans les années 40 à s'intéresser à la manière par laquelle une machine pourrait se reproduire, c'est à dire produire une copie d'elle-même.

A une époque où l'ADN n'avait pas encore été reconnu comme le matériau génétique de la nature, Von Neumann souhaite mieux comprendre la logique qui sous-tend les phénomènes auto-réplicatifs ou auto-reproductifs.

"... living organisms are very complicated aggregations of elementary parts, and by any reasonable theory of probability or thermodynamics highly improbable. That they should occur in the world at all is a miracle of the first magnitude; the only thing which removes, or mitigates, this miracle is that they reproduce themselves. Therefore, if by any peculiar accident there should ever be one of them, from there on the rules of probability do not apply, and there will be many of them, at least if the milieu is reasonable." John Von Neumann, Theory of Self-Reproducing Automata. Source : The artificial Self-replication page byMoshe Sipper.

A quoi cela peut-il bien servir ?

L'objectif des chercheurs dans ce domaine est de comprendre les principes de création d'information ainsi que d'éclaircir les algorithmes impliqués dans l'auto-reproduction.

Comprendre ces principes permet d'en savoir plus sur les phénomènes biologiques du même nom, en clarifiant par exemple les conditions nécessaires à tout modèle auto-replicatif, ou en fournissant une explication alternative à des phénomènes observés.

Pourquoi les automates cellulaires ?

La simplicité des automates cellulaires et leur modèle mathématique rigoureux y sont pour beaucoup dans le choix de Von Neumann de privilégier les automates cellulaires comme moyen d'investigation des processus auto-reproductif.

La machine universelle de Von Neumann

Von Neumann a utilisé un automate cellulaire bidimensionnel à 29 états avec un voisinage de 5 cellules (cellule cible + 4 voisines contigües). Il a montré qu'une machine universelle pouvait être embarquée dans une telle architecture. Il a également décrit comment un constructeur universel pouvait être construit. C'est à dire une structure capable de générer n'importe quelle configuration stockée dans une structure de stockage (tape), via un bras constructeur.

Un schéma de la machine universelle de Turing de Von Neumann

Un tel constructeur est également capable de générer une copie de lui-même, c'est à dire de s'auto-répliquer.

Les mécanismes que VN a mis en évidence pour l'auto-reproduction des automates cellulaires présentent de fortes ressemblance avec ceux employés dans les processus biologiques découverts une dizaine d'années après.

La boucle auto-réplicante de Langton

Langton remarque que l'auto-reproduction n'est qu'une des caractéristiques de la machine universelle de Turing.

Une "machine" plus simple peut s'auto-reproduire sans toutefois satisfaire aux conditions de construction universelle d'une machine de Turing.

De plus, les systèmes vivants ne sont probablement pas capable de construction universelle. Langton décide donc de développer un automate auto-réplicatif plus simple que celui de VN. Il se base donc sur les travaux de E. F. Codd, et réutilise son automate cellulaire à 8 états - voisinage de 5 cellules, simplification de celui de VN.

La 'machine' de base est une boucle constituée de 86 cellules, formant un conduit de circulation de données fermé (cellules bleues), entouré par une gaine (cellules rouges).

La structure de base comprend également un bras de projection qui permet sa duplication.

Le conduit permet la circulation de l'information sous forme de signaux : couples de cellules (bleu clair-noir ou jaune-noir), qui constituent en fait le matériau génétique de la structure (génôme) et en permet la reproduction.

Au moment ou les signaux rencontrent la jonction avec le bras de projection, ils sont dupiqués. Une copie est renvoyée dans la boucle, et l'autre copie se propage le long du bras. C'est l'équivalent de la transcription du processus biologique. En arrivant au bout du bras, les signaux sont transformés en instructions. C'est l'équivalent de la translation du processus biologique.

Le bras s'étend selon ces même instructions pour former une autre structure similaire à la première et contenant le même patrimoine informationnel permettant la réplication.

Les images qui précèdent sont des copies d'écran d'une applet JAVA présente sur le site : Self-Replication loops in Cellular Space.