LA VIE ARTIFICIELLE; AUTOMATES CELLULAIRES
Autoreproduction
L´autoreproduction des machines selon Von Neumann
En 1950 le mathématicien John Von Neumann se demanda si une
machine pouvait se duppliquer elle-même et si cette copie
pourrait être plus élaborée que son original, en d´autres termes
il se posa la question d´une évolution des machines considerées
somme une espèce "vivante" [Von Neumann 66].
Pour cela il conçut ce qu´il appelait
un copieur universel capable de fabriquer n´importe quelle
structure à partir d´une description de celle-ci. Si on fournissait
à ce copieur une description de lui-même pourrait-il se copier,
c´est à dire se reproduire ? Mais une telle description devrait
comporter le copieur ainsi que sa description et on arrive à
une définition récursive en abîme c´est à dire irréalisable
en un temps fini. Pour résoudre ce paradox, Von Neumann construisit
un modèle abstrait le plus simple possible sous la forme d´un
damier plan infini dont chaque case était caractérisée par
29 états (notés de 0 à 28)
ne dépendant que de ses 4 voisines orthogonales,
il définit ensuite des règles de transition d´un état à un autre
et montra que certains motifs sont capables de se reproduire.
Le processus était contrôlé par une machine universelle de Turing.
Dans un premier temps le "copieur-supervisuer" (constitué du copieur
universel et de la machine de Turing) réalise une copie de lui-même
en exécutant sa propre description, lorsqu´il arrive à celle-ci,
il cesse de l´interpreter pour n´en faire qu´une copie littérale.
Copie du copieur superviseur
Copie de la description
Motifs géométriques autogénérés
En 1950 John Von Neumann s´intéressa au problème de
l´autoreproduction des machines [Von Neumann 66], il pensait qu´à partir d´une
certaine complexité de telles machines pourraient manifester des
propriétés du vivant. Il n´existait pas, à l´époque, de technologie
suffisamment puissante pour implementer ces idées. Ulam [Ulam 76]
étudiait des "jeux mathématiques" consistant à faire se développer
automatiquement des formes géométriques sur des écrans d´ordinateurs.
La règle du jeu le plus simple est: Si une cellule a une voisine
activée, elle s´active elle-même. Il est facile de constater,
qu´à partir d´une unique cellule active placée au centre de l´écran,
celui-ci se couvre peu à peu de cellules actives.
Un jeu un peu plus complexe consiste à appliquer la règle: Une cellule
ne devient active que si elle n´a qu´une seule voisine (à l´exclusion
de celles situées dans les diagonales). Il apparait un motif en forme
de "corail".
Il est facile d´inventer des systèmes de règles produisant des
graphismes surprenants.
Le jeu de la vie
John Horton Conway inventa en 1970 le jeu de la vie
[Gardner 83]. Il est construit sur 2 règles:
1) Une cellule entourée par 3 cellules actives devient active.
2) Une cellule active meurt si elle possède moins de 2 ou plus
de 3 cellules voisines actives.
Ces règles traduisent, de façon élémentaire, l´autoreproduction
(naissance dans un environnement assez riche), l´autoconservation
(mort si l´environnement est trop pauvre ou trop riche).
Certaines structures initiales donnent lieu à des motifs stables,
d´autres périodiques. Voici quelques exemples:
Clignotant
Ruche
Planeur
Feu de signalisation
Malgré la simplicité de ses règles le jeu de la vie est
capable de simuler la machine universelle de Turing, c´est à dire
tout ordinateur, en effet, à partir de certains états initiaux,
il est possible de générer des portes logiques.
Les automates de Langton
En 1984 Christopher Langton [Langton 86] conçut un
automate autoreproducteur sur le modèle de celui de Von Neumann
mais ne comprenant plus que 8 états (au lieu de 29): Il est constitué
d´une membrane de cellules à l´état 2 enfermant un noyau constitué d´une
chaîne de cellules d´états 0, 1, 4 et 7 représentant son programme
d´autoreproduction (son matériel génétique). À chaque cycle les mots
constitués d´un couple (a,b) se propagent vers la queue, au bout
le mot (7,0) ajoute le mot (4,0) qui débute une nouvelle chaîne à angle
droit. Lorsque la boucle rencontre la membrane il y a rupture de
l´automate en 2 automates identiques et la reproduction peut se
poursuivre ainsi indéfiniement.
État initial
Première croissance horizontale
Croissance horizontale
Croissance verticale
Croissance verticale
Croissance horizontale
Croissance verticale
Jonction
Deux nouveaux automates
Nouvelles croissances
Afin de simuler la croissance des récifs coralliens, Neumann
a ajouté une règle de transition arrêtant le développement d´un
automate après un certain nombre de cycles.
Réseaux d´automates
Un réseau d´automates est un système discret évoluant en fonction
des interactions entre ses éléments, on les utilise dans la
modélisation des systèmes continus dynamiques régis par des
équations différentielles. Pour cela on applique une méthode linéaire
qui discrétise le temps et utilise des automates à états finis
dont les fonctions de transition déterminent le comportement du
réseau. Dans un fonctionnement parallèlle tous les
automates basculent d´un état dans un autre au même instant,
alors que dans un fonctionnement séquentiel les automates
sont modifiés les uns après les autres dans un ordre prédéterminé
ou aléatoire.
Dans un réseau d´automates cellulaires les connexions sont
limitées à un voisinage de chaque élément, dans un réseau complet
chaque automate est connecté à tous les autres. Le système est
dit ouvert si certaines cellules reçoivent leurs entrées
de l´extérieur, sinon il est dit fermé. Le réseau peut
être une grille à mailles triangulaires, carrées, hexagonales
ou quelconques, il peut être borné, les bords pouvant être périodiques
(cylindre, tore, sphère, ...).
Lorsque les fonctions de transition ne sont pas déterministes
mais aléatoires on parle d´automates probabilistes, ils sont
définis par une énergie et une température (voir
les
machines de Boltzmann.
Dans un réseau non trivial les fonctions de transition
elles-mêmes changent lorsque les automates changent d´état.
Un réseau d´automates cellulaires modélisent de façon
simplifiée le concept de Vie Artificielle:
1) En tant que systèmes dynamiques non linéaires ils
permettent de simuler toutes sortes de systèmes physiques réels.
2) Un comportement complexe peut émerger de l´interaction de
ses éléments sans qu´aucun d´eux ne manifeste un tel comportement,
se rapprochant par là des organismes vivants.
On peut envisager la Vie, non pas du seul point de vue
biologique (définie par son seul support actuellement connu), mais
plutôt comme émergence d´une structure complexe
définie par les interactions entre des éléments simples. Cette
définition de la vie s´applique aussi bien à la Vie Naturelle
qu´à la Vie Artificielle, les deux n´étant que des
manifestations différentes d´une même réalité.