au sommaire
Auto-reproduction des 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 NeumannJohn 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'ADNADN n'avait pas encore été reconnu comme le matériau génétiquegé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 cellulairesautomates 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 universelconstructeur 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 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 constructionconstruction 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 transcriptiontranscription 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éplicationréplication.
Les images qui précèdent sont des copies d'écran d'une applet JAVAJAVA présente sur le site : Self-Replication loops in Cellular Space.
par Jérôme Damelincourt
le 18 octobre 2003
