Le jeu de la vie et l'émergence de la complexité
et les différentes classes d'automates cellulaires
Sommaire
Règles du jeu
Sur une grille de taille variée voire infinie, on dispose au hasard des pions qui symbolisent les cases vivantes. Les cases qui ne comportent pas de pions représentent au contraire des cases mortes. Conway propose quelques lois simples pour faire évoluer ce système qui dépendent du nombre de voisins qu’a chaque pion :- Pour survivre, un pion doit avoir deux ou trois voisins dans les huit cases qui l’entourent. S’il en a plus il meurt de surpopulation, s’il en a moins, il meurt d’isolement.
- Une case vide qui a exactement trois voisins permet de faire apparaître un nouveau pion
Des comportements collectifs émergents
Les résultats sont parfois surprenants. Il "émerge" de ces règles simples appliquées aux pions individuels des comportements collectifs. Il permet de voir apparaitre visuellement des propriétés émergentes.Wikipédia propose un ensemble d'articles sur le jeu de la vie. On y trouve par exemple la configuration du Planneur : un ensemble de 5 pions disposés d'une manière particulière et qui au bout de 4 étapes du jeu de la vie se retrouve à l'identique mais déplacés dans la grille.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/GameOfLife_Glider_Animation.gif/100px-GameOfLife_Glider_Animation.gif)
Emergence et réductionnisme
On oppose souvent l'émergence au réductionnisme sur lequel est fondée la science.- Le réductionnisme, au sens fort, élimine les propriétés apparentes d'un système pour les remplacer par les processus élémentaires sous-jacents
- L'émergence au contraire part du fait que "le tout est plus que la somme des parties"
Les automates cellulaires
Les règles du jeu de la Vie conduisent à un comportement complexe. Mais si on change les règles du jeu le comportement change. Ce genre de fonctionnement où des pions appliquent des règles simples sur une grille est appelé "automates cellulaires de dimension 2" (la dimension d'une grille plate). On peut retrouver dans ce cas les différents types d'automates cellulaires identifiés par Stephen Wolfram dans son livre "a new kind of science". Dans son cas, il s'est "limité" aux 256 automates cellulaires binaires de dimension 1, ce qui lui permet de distinguer 4 types d'automates cellulaires. Les automates cellulaires binaires de dimension 2 permettent eux 1296 règles différentes du type :- si une cellule à l'état 1 est entourée par X Cellules à l'état 1 avec Eb<=X<=Eh alors elle conserve son état
- si une cellule à l'état 0 est entourée par Y Cellules à l'état 1 avec Fb<=Y<=Fh alors elle passe à l'état 1
- Dans tous les autres cas elle passe à 0
Les classes d'automates cellulaires
- Classe 1 : évolution vers un état fixe et homogène (par exemple la grille complètement vierge ou encore complètement couverte de pions) (dynamiques ordonnées)
- Classe 2 : évolution vers des structures stables ou périodiques (il peut y avoir des structures locales qui oscillent entre deux états différents, insérées dans ne structure globalement stable) (dynamiques ordonnées cycliques)
- Classe 3 : évolution vers une succession de configurations arbitraires : toutes les générations sont localement différentes mais globalement et statistiquement semblables (par exemple la proportion de cellules à l'état 1) (dynamiques désordonnées)
- Classe 4 : évolution vers un système complexe ou des structures émergent (comme dans le jeu de la vie ou on trouve par exemple des planneurs et des possibilités de simuler une machine de Turing) (dynamiques complexes à mi-chemin entre les dynamiques ordonnées et désordonnées)
La complexité (classe IV) entre l'ordre et le desordre
La complexité apparait à mi-chemin entre l'ordre et le désordre. Au lieu d'avoir un désordre qui s'acroit continuemment à partir de l'ordre, on observe à un moment une augmentation de la complexité jusqu'à un seuil - une transition de phase - où elle décroit ensuite. En physique un système subit une modification profonde de certaines de ses propriétés pendant une transition de phase. Avant et après, on a une certaine forme de stabilité dynamique, mais pendant la transition, lorsque la complexité est maximale, on se retrouve loin de l'équilibre (voir les structures dissipatives de Ilya Prigogine).La question est de savoir jusqu'à quel niveau de complexité on peut aller. cela revient à étudier la capacité de traitement de l'information du système. Certains automates comme celui du jeu de la vie peuvent simuler une machine de Turing, c'est à dire sont potentiellement capable de traiter n'importe quel problème (propriété de computation universelle). Cela veut dire que le jeu de la vie, par exemple, peut être utilisé comme un ordinateur pour traiter des problèmes (pour cela il dispose de structures qui permettent de produire des signaux - les "canons à glisseurs" - qui peuvent se propager - "planneurs", et être triatés par des types de portes ET, OU ou NON (démonstration faite par Elwyn Berlekamp, John Conway et Richard Guy en 1982).
En fait les automates de classe IV sont les seuls à combiner à la fois des carastérisitique des classes I et II
(stokage de l'information sous forme d'attracteurs) et de la classe III (transmission de l'information mais en détruisant l'état antérieur).
les reseaux d'agents
le modèle des réseaux d'agent est plus général que les automates cellulaires. Les agents sont des programmes indépendants - identiques ou non - caractérisés par- un ensemble d'attributs qui déterminent leur état,
- un ensemble de fonctions définissant les lois d'interaction entre les agents.
- Aucun agent ne contrôle directement les autres agents
- Aucune règle globale ne dicte le comportement du système
- Les structures et dynamiques globales émergent desinteractions entre agents
"C'est chaque fois le même phénomène, il y a création d'un champ de possibles extrêmement large, puis le choix d'une trajectoire de stabilisation qui mène à l'ordre (attracteurs de type points fixes ou périodiques) ou au chaos (attracteurs chaotiques). Pourtant, dans certaines conditions, des structures réussissent à échapper à ces puissant attracteurs en se maintenant à leur frontière. Grâce à leur capacité de mémorisation et de traitement de l'information, elles s'adaptent et évoluent au niveau de cette transition de phase. Elles résistent aisni mieux que d'autres aux fluctuations du milieu et préservent leur "identité" dans l'espace et le temps" (Jean-Claude Heudin)
Automates et matière
On peut assimiler les automates cellulaires à une sorte de matière virtuelle dont on fixe les lois de la physique : des interactions entre des unités simples mais en très grand nombre font émerger des comportements complexes. On pourrait assimiler les différentes classes de dynamiques (ordonnées, desosronnées et complexes) avec différentes phases de la matière.A partir de : Jean-Claude Heudin, "le jeu de la vie", in Sciences et Avenir Hors Série n°143 sur "l'énigme de l'émergence" juillet/août 2005.
Deux sites pour tester le jeu de la vie : http://www.univ-lemans.fr/enseignements/physique/02/divers/conway.html et http://www.vieartificielle.com/article/?id=91
Complexité / Demains - possibles / Demains - choisir.
Par J-M Cornu
| Avant
| 02/09/2005 07:03
| Après
| Complexité
|
2 commentaires
| Lu 11778 fois
|
par Cornu, le Mercredi 21 Septembre 2005, 16:25
Répondre à ce commentaireJe me permets de vous proposer un lien vers un
petit bidouillage autour du jeu de la vie...
Très intéressant de pouvoir tester des automates programmables à deux dimension avec plus de deux états !
Comment fonctionne la règle ?
- Les voisins min et max à avoir pour qu'une cellule vivante reste vivante : la règle est-elle valable pour chacun des états ?
- idem pour le parents min et max pour qu'une cellule morte devienne vivante ?
Que se passe-t-il avec les voirsins (ou parents) d'autres couleur ? Un état a-t-il priorité sur un autre lorsque les règles lui permettent de vivre par exemple en vert ET en rouge ?
En tout cas j'ai pu constater (un peu par hasard je dois l'avouer ;-) que l'on peut avoir des glisseurs multi-états et avec un grand nombre de cellules du plus bel effet...Je ne connaissais pas "the recursive universe" de William Pounstone. je vois qu'il est de 1985. Introduit-il des choses supplémentaires en particulier par rapport à des travaux postérieurs cmme ceux de Stephen Wolfram (A new Kind of Science ?) ou ceux de Jean-Claude Heudin sur le fait que l'on retrouve les 4 classes d'automates cellulaires de Wolfram lorsque l'on est en 2 dimensions ?Sinon : vous avez lu "The Recursive Universe"
de William Pounstone ?
Je m'intéresse beaucoup à ce sujet car il est abordé dans le chapitre 2 que je viens juste de termineer de mon futur livre "demain(s) - La science et le choix des possibles" qui montre différents aspects imprévisibles (mais déterministes) en science. Et là je regarde de près les aspects indéterminés pour le chapitre 3 (principalement Gödel en mathématiques et Epiménide en philosophie...).
Je m'interroge aussi dans ce chapitre à écrire pour savoir si la physique quantique est un phénomène indéterminé (comme le laisse à penser l'école de Copenhague et les expériences autour du paradoxe EPR) ou bien s'il s'agit d'un phénomène imprévisible mais déterministe comme les automates cellulaires ?
Commentaires
1 - Life, poundstone & bidouillepar Denis van Waerebeke, le Mercredi 21 Septembre 2005, 13:01 Répondre à ce commentaire