|
|
|
---
|
|
|
|
|
|
|
|
<!-- TOC depthFrom:1 depthTo:6 withLinks:1 updateOnSave:0 orderedList:1 -->
|
|
|
|
|
|
|
|
- [Automates cellulaires](#automates-cellulaires)
|
|
|
|
- [Description](#description)
|
|
|
|
- [Automates de dimension 1](#automates-de-dimension-1)
|
|
|
|
- [Classes d'automate](#classes-dautomate)
|
|
|
|
- [Classification de Wolfram](#classification-de-wolfram)
|
|
|
|
- [Exercice](#exercice)
|
|
|
|
- [Automates de dimension 2](#automates-de-dimension-2)
|
|
|
|
- [Le jeu de la vie](#le-jeu-de-la-vie)
|
|
|
|
- [Exercice](#exercice)
|
|
|
|
- [Pour aller plus loin](#pour-aller-plus-loin)
|
|
|
|
- [Automates cellulaires réversibles](#automates-cellulaires-réversibles)
|
|
|
|
- [Automates réversibles de bloc](#automates-réversibles-de-bloc)
|
|
|
|
- [Exercice](#exercice)
|
|
|
|
- [Automates auto-réplicatifs](#automates-auto-réplicatifs)
|
|
|
|
- [La boucle de Langton](#la-boucle-de-langton)
|
|
|
|
- [Exercice](#exercice)
|
|
|
|
- [Pour aller plus loin](#pour-aller-plus-loin)
|
|
|
|
- [Conception](#conception)
|
|
|
|
- [Vocabulaire](#vocabulaire)
|
|
|
|
- [Notes et références](#notes-et-références)
|
|
|
|
|
|
|
|
<!-- /TOC -->
|
|
|
|
---
|
|
|
|
|
|
|
|
|
|
|
|
# Automates cellulaires
|
|
|
|
|
|
|
|
> Comment des interactions simples entre des entités extrêmement simples peuvent-elles engendrer des comportements complexes, jusqu'à des mécanismes auto-reproducteurs ?
|
| ... | ... | @@ -11,14 +40,14 @@ Les automates cellulaires sont des modèles abstraits simulant le fonctionnement |
|
|
|
|
|
|
|
Les automates cellulaires ont été proposés dans les années 1950 par John von Neumann suite à une suggestion de son ami le mathématicien Stanislaw Ulam. Alors qu'il s'interrogeait sur comment concevoir une machine capable de s'auto-reproduire, Ulam l'orienta vers une question moins vaste : quelle organisation logique est suffisante pour un automate pour être capable de s'autoreproduire ?
|
|
|
|
|
|
|
|
Von Neumann fait alors le choix de considérer le problème dans un espace mathématique simple, métaphore du monde réel. L'espace est une grille régulière composée de cellules qui ont un état choisi dans un ensemble fini d'états possibles. L'évolution se fait à chaque pas de temps en fonction de règles locales.
|
|
|
|
Von Neumann fait alors le choix de considérer le problème dans un espace mathématique simple, métaphore du monde réel. L'espace est une grille régulière composée de cellules qui ont un état choisi dans un ensemble fini d'états possibles. L'évolution se fait à chaque pas de temps en fonction de règles locales.
|
|
|
|
|
|
|
|
Cette vision initiera tout un développement encore très actif autour des automates cellulaires, c'est ce que nous allons exposer partiellement dans la suite.
|
|
|
|
|
|
|
|
|
|
|
|
## Description
|
|
|
|
Les automates cellulaires sont des machines à états finis évoluant sur une grille infinie, le plus souvent, et de dimension `n`. Les dimensions habituelles sont généralement 1 ou 2. La grille définit un espace discret et un voisinage pour chacune des cases de la grille. Cette grille peut être régulière ou non et les cases peuvent prendre différentes formes (carrée, hexagonale ....).
|
|
|
|
On associe à chaque case de la grille une **cellule**, cette dernière va alors avoir un état, ce dernier est déterminé par l'état de la cellule considérée, le voisinage et une règle de transition. L'automate cellulaire évolue en fonction de ces modifications qui peuvent se faire de façon synchrone ou asynchrone. Dans ce qui suit nous considérerons uniquement le premier cas.
|
|
|
|
Les automates cellulaires sont des machines à états finis évoluant sur une grille infinie, le plus souvent, et de dimension `n`. Les dimensions habituelles sont généralement 1 ou 2. La grille définit un espace discret et un voisinage pour chacune des cases de la grille. Cette grille peut être régulière ou non et les cases peuvent prendre différentes formes (carrée, hexagonale ....).
|
|
|
|
On associe à chaque case de la grille une **cellule**, cette dernière va alors avoir un état, ce dernier est déterminé par l'état de la cellule considérée, le voisinage et une règle de transition. L'automate cellulaire évolue en fonction de ces modifications qui peuvent se faire de façon synchrone ou asynchrone. Dans ce qui suit nous considérerons uniquement le premier cas.
|
|
|
|
|
|
|
|
Soit
|
|
|
|
* $`L`$ un réseau régulier (ses éléments sont des cellules) ;
|
| ... | ... | @@ -44,28 +73,28 @@ Considérons un ruban infini des deux cotés, subdivisé en cellules. Chaque cel |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chaque cellule va alors changer de couleur en fonction de la couleur de ses voisines. L’évolution d'un automate cellulaire de dimension 1 est alors représenté par un diagramme espace-temps.
|
|
|
|
Chaque cellule va alors changer de couleur en fonction de la couleur de ses voisines. L’évolution d'un automate cellulaire de dimension 1 est alors représenté par un diagramme espace-temps.
|
|
|
|
|
|
|
|
Si on défini on a la fonction de transition suivante : une cellule est coloriée en bleu au temps $`t+1 `$ si au temps $`t`$, parmi les deux cellules voisines immédiates, à sa gauche et à sa droite, il y a exactement une cellule bleue. L'état initial est constitué d’un ruban blanc avec une seule cellule bleue. On obtient le diagramme espace-temps suivant :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cela n'est pas sans rappeler les triangles de Sierpiński !
|
|
|
|
Cela n'est pas sans rappeler les triangles de Sierpiński !
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
En effet certains automates exhibent des diagrammes espaces-temps fractaux.
|
|
|
|
|
|
|
|
|
|
|
|
### Classes d'automate
|
|
|
|
### Classes d'automate
|
|
|
|
|
|
|
|
Wolfram [^1] s'est penché sur le cas des automates de dimension 1 à deux états, en considérant le voisinage immédiat. Pour une case donnée il reste donc à définir l'évolution. On peut rapidement se convaincre qu'il n'y a que 8 états à considérer :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Il n’y a donc que $`2^8=256`$ règles possibles. On attribue à chaque règle la représentation en binaire de sa définition par des cases noires et blanches.La régle présentée ici est donc $`11111110_2 = 254_{10}`$.
|
|
|
|
|
|
|
|
Dans son [atlas](http://atlas.wolfram.com/01/01/), Wolfram
|
|
|
|
Dans son [atlas](http://atlas.wolfram.com/01/01/), Wolfram
|
|
|
|
énumère et étudie les différentes règles.
|
|
|
|
|
|
|
|
|
| ... | ... | @@ -97,13 +126,13 @@ Si l'on regarde son évolution sur la droite il reste totalement blanc sur la dr |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Le motif bien qu'ayant l’air régulier, il apparait et disparait des séries de triangles blanc qui se propagennt et des bandes noires diagonales. Ces structures semblent interagir : elles apparaissent, se rencontrent, disparaissent. [Cook a montré](http://www.complex-systems.com/pdf/15-1-1.pdf) que cela constituait une machine universelle, cela implique que n'importe quel programme peut être simulé sur cet automate.
|
|
|
|
Le motif bien qu'ayant l’air régulier, il apparait et disparait des séries de triangles blanc qui se propagennt et des bandes noires diagonales. Ces structures semblent interagir : elles apparaissent, se rencontrent, disparaissent. [Cook a montré](http://www.complex-systems.com/pdf/15-1-1.pdf) que cela constituait une machine universelle, cela implique que n'importe quel programme peut être simulé sur cet automate.
|
|
|
|
|
|
|
|
#### Classification de Wolfram
|
|
|
|
#### Classification de Wolfram
|
|
|
|
|
|
|
|
Ces classes sont encore discutées, néanmoins elles suffisent pour notre propos. Wolfram a proposé quatre classes de complexité pour les automates cellulaires en fonction leur diagramme espace-temps.
|
|
|
|
|
|
|
|
* La classe 1, le comportement est monotone, il produisent un motif homogène. Pratiquement toutes les configurations initiales conduisent à la même configuration fixe et homogène.
|
|
|
|
* La classe 1, le comportement est monotone, il produisent un motif homogène. Pratiquement toutes les configurations initiales conduisent à la même configuration fixe et homogène.
|
|
|
|
* La classe 2, le comportement est plus sophistiqué. Pratiquement toutes les configurations initiales conduisent à des configurations qui se répètent périodiquement. La périodicité constatée souvent ne fait que refléter la configuration initiale, néanmoins certains automates cellulaires de classe 2 ont des diagrammes espace-temps sans que la configuration initiale le soit.
|
|
|
|
* La classe 3, le comportement semble chaotique. Leurs diagrammes espace-temps semblent irréguliers. Ils ont généralement une grande sensibilité aux conditions initiales : une légère modification de la configuration initiale change fortement les diagrammes ou semble avoir des conséquences très lointaines.
|
|
|
|
* La classe 4, il y a émergence de structures localisées avec des interactions
|
| ... | ... | @@ -112,13 +141,13 @@ complexes. Ce type d'automate se rapproche fortement des définitions de la vie |
|
|
|
|
|
|
|
#### Exercice
|
|
|
|
|
|
|
|
Réaliser en NetLogo une étude de ces automates à 1 dimension à 2 états. On écrira le programme le plus général possible auquel on fournira la règle et la situation initiale.
|
|
|
|
Réaliser en NetLogo une étude de ces automates à 1 dimension à 2 états. On écrira le programme le plus général possible auquel on fournira la règle et la situation initiale.
|
|
|
|
|
|
|
|
|
|
|
|
## Automates de dimension 2
|
|
|
|
|
|
|
|
Un automate cellulaire de dimension 2 correspond à une description d'un univers de dimension 2 dont les lois sont déterministes et locales. L'espace est constitué d'un plan pavé de façon régulière par des polygones réguliers, le plus souvent. Dans le cas d'un plan euclidien, il s'agit alors soit de triangles équilatéraux, de carrés ou d'hexagones.
|
|
|
|
Les cellules remplissent entièrement l'espace à 2 dimensions et le pavage est périodique,
|
|
|
|
Les cellules remplissent entièrement l'espace à 2 dimensions et le pavage est périodique,
|
|
|
|
|
|
|
|
 
|
|
|
|
|
| ... | ... | @@ -163,23 +192,23 @@ L'exemple le plus simple est le clignotant . C'est le plus petit vaisseau du jeu de la vie : cinq cellules contenues dans un carré de trois cellules sur trois. Il se déplace d'une case en diagonale toutes les quatre générations.
|
|
|
|
Le planeur est l'exemple le plus connu (cf. ci-dessous). C'est le plus petit vaisseau du jeu de la vie : cinq cellules contenues dans un carré de trois cellules sur trois. Il se déplace d'une case en diagonale toutes les quatre générations.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[*Les mathusalems*](https://fr.wikipedia.org/wiki/Mathusalem_(automate_cellulaire))
|
|
|
|
|
|
|
|
Ce sont des structures qui "explosent" en structures stables. Le R-pentamino trouvé par Conway lui-même est un exemple. C'est d'ailleurs à partir de ce dernier que le planeur a été trouvé.
|
|
|
|
Ce sont des structures qui "explosent" en structures stables. Le R-pentamino trouvé par Conway lui-même est un exemple. C'est d'ailleurs à partir de ce dernier que le planeur a été trouvé.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
*Système complexe*
|
|
|
|
La combinaison de structure amène une dimension supplémentaire, encore. Le jeu de la vie présente toute les caractéristiques d'un système complexe. Bien que les règles soient d'une simplicité absolue, on observe des comportements complexes et des caractérisques liées aux systèmes complexes : l'auto-organisation, l'émergence et une trajectoire non prévisible.
|
|
|
|
La combinaison de structure amène une dimension supplémentaire, encore. Le jeu de la vie présente toute les caractéristiques d'un système complexe. Bien que les règles soient d'une simplicité absolue, on observe des comportements complexes et des caractérisques liées aux systèmes complexes : l'auto-organisation, l'émergence et une trajectoire non prévisible.
|
|
|
|
|
|
|
|
|
|
|
|
Ainsi lorsque l'on part d'une configuration aléatoire après un certains nombres d'itérations, le système ne présente plus une répartition aléatoire. Il y a des zones vides, des zones "calmes et stables" et d'autres encore en évolution. Cela témoigne d'une forme d'auto-organisation. L'émergence est elle présente dans les R-pentaminos qui génèrent des planeurs qui se déplacent dans l'espace sans que cela ait été spécifié/codé par les règles. On pourrait vouloir décrire le comportement global du système mathématiquement, mais cela s'avère difficile voire impossible, ainsi on conjecture qu'aucune méthode dans le cas d'une grille infinie ne sera plus efficace que la simulation.
|
|
|
|
Ainsi lorsque l'on part d'une configuration aléatoire après un certains nombres d'itérations, le système ne présente plus une répartition aléatoire. Il y a des zones vides, des zones "calmes et stables" et d'autres encore en évolution. Cela témoigne d'une forme d'auto-organisation. L'émergence est elle présente dans les R-pentaminos qui génèrent des planeurs qui se déplacent dans l'espace sans que cela ait été spécifié/codé par les règles. On pourrait vouloir décrire le comportement global du système mathématiquement, mais cela s'avère difficile voire impossible, ainsi on conjecture qu'aucune méthode dans le cas d'une grille infinie ne sera plus efficace que la simulation.
|
|
|
|
|
|
|
|
Le jeu de la vie est irréversible. Il n'est pas possible de déterminer des règles permettant de déduire d'une configuration donnée au pas de temps $`i`$ la configuration à l'état $`i-1`$, pour s'en convaincre, il suffit de regarder quelles sont les configurations antérieures qui conduisent à un carré de 4 cellules.
|
|
|
|
|
| ... | ... | @@ -198,12 +227,12 @@ Dans le bestiaire du jeu de la vie ces structures ne sont pas anodines, elles pe |
|
|
|
|
|
|
|
#### Exercice
|
|
|
|
|
|
|
|
Vous n'y couperez pas ! Vous devez programmer le jeu de la vie.
|
|
|
|
Vous n'y couperez pas ! Vous devez programmer le jeu de la vie.
|
|
|
|
|
|
|
|
Plusieurs possibilités doivent être offertes à l'utilisateur. Vous devez commencer par concevoir un premier programme du jeu de la vie. Ce programme devra demander à l’utilisateur le taux d’occupation initial et s'il fait le choix d'une génération aléatoire de départ ou d'une configuration qu'il fournira soit à l'aide de l'interface, soit à l'aide d'un fichier. Ensuite, l’utilisateur pourra choisir si le programme fera évoluer la grille pas par pas, ou si la simulation sera effectuée pour un nombre de pas de temps donné (choisi par l’utilisateur) ou à l'infini.
|
|
|
|
La simulation devra se dérouler sur un tore.
|
|
|
|
La simulation devra se dérouler sur un tore.
|
|
|
|
Le programme devra alors pouvoir afficher, durant la simulation, une courbe présentant l’évolution du taux d’occupation de la grille en fonction du temps.
|
|
|
|
|
|
|
|
|
|
|
|
Les fichiers seront encodés sur le format `lif` 1.06. Vous pourrez en trouver une description [ici](http://www.conwaylife.com/w/index.php?title=Life_1.06) et un zoo de structures sur le même [site](http://www.conwaylife.com/wiki/Category:Patterns). Si d'aventure vous voulez tester une autre configuration dans un autre format, vous pouvez toujours utiliser le [convertisseur](http://lifeconvert.wayneandlayne.com/) de Adam Wolf and Matthew Beckler.
|
|
|
|
|
|
|
|
|
| ... | ... | @@ -215,16 +244,16 @@ Vous pouvez chercher à détecter automatiquement une extinction, une structure |
|
|
|
Pour certaines configurations on arrive à $`10^{50}`$, il n'est plus question d'utiliser un algorithme qui parcourt la totalité des grilles étudiées (elles ne sont pas nécessairement bornées ....). Il faut donc être plus malin, un premier [algorithme Hashlife](https://fr.wikipedia.org/wiki/Hashlife) avait été proposé par Bill Gosper. Il exploite la redondance spatiale et temporelle des structures et utilise des quadtrees. Cet algorithme tourne ou plutôt tournait sur des machines LISP. [Golly](https://sourceforge.net/projects/golly/) a repris le flambeau et c'est cet algorithme qui a d'ailleurs été utilisé pour la simulation du jeu de la vie dans le jeu de la vie.
|
|
|
|
|
|
|
|
|
|
|
|
#### Automate cellulaire réversible
|
|
|
|
### Automates cellulaires réversibles
|
|
|
|
|
|
|
|
On veut maintenant construire un automate qui puisse "remonter dans le temps" de façon déterministe. Les règles de transition d'un tel automate doivent donc être réversible. Nous l'avons déjà dit, le jeu de la vie n'est pas réversible. L'existence des jardins d'Eden en est la preuve. Nous allons donc considérer les automates réversibles de bloc.
|
|
|
|
|
|
|
|
|
|
|
|
#### Automates réversibles de bloc
|
|
|
|
|
|
|
|
Les automates réversibles de bloc sont des automates particuliers. Le pavage de l'espace est divisé en blocs ne se chevauchant pas. Cette division varie suivant les étapes de temps, la partition de l'espace n'est donc pas la même à $`t = i`$ qu'à $`t = i + 1`$. Les règles de transition sont elles appliquées à un bloc entier plutôt qu'à une unique cellule. Ces automates sont utilisés en particulier dans les simulations physiques car il est possible de définir des règles de transition qui permette de respecter la réversibilité et les lois de conservation.
|
|
|
|
Les automates réversibles de bloc sont des automates particuliers. Le pavage de l'espace est divisé en blocs ne se chevauchant pas. Cette division varie suivant les étapes de temps, la partition de l'espace n'est donc pas la même à $`t = i`$ qu'à $`t = i + 1`$. Les règles de transition sont elles appliquées à un bloc entier plutôt qu'à une unique cellule. Ces automates sont utilisés en particulier dans les simulations physiques car il est possible de définir des règles de transition qui permette de respecter la réversibilité et les lois de conservation.
|
|
|
|
|
|
|
|
Un automate réversible de bloc est composé de :
|
|
|
|
Un automate réversible de bloc est composé de :
|
|
|
|
|
|
|
|
* une grille régulière de cellules ;
|
|
|
|
* un ensemble fini d'états dans lesquels chaque cellule peut être ;
|
| ... | ... | @@ -243,9 +272,9 @@ Un calcul informatique $`y = f(x)`$ est réversible, si la donnée d'entrée $`x |
|
|
|
|
|
|
|
*Propriétés d'un voisinage de Margolus*
|
|
|
|
|
|
|
|
Si vous considérez le voisinage proposé, si vous translatez verticalement ou horizontalement d'un nombre impair de cellule vous n'obtiendrez pas en général le même comportement, ce qui n'est pas le cas du jeu de la vie. Ceci est du à la structure par bloc.
|
|
|
|
Si vous considérez le voisinage proposé, si vous translatez verticalement ou horizontalement d'un nombre impair de cellule vous n'obtiendrez pas en général le même comportement, ce qui n'est pas le cas du jeu de la vie. Ceci est du à la structure par bloc.
|
|
|
|
|
|
|
|
De la même façon un décalage dans le temps d'un nombre impair modifie le comportement de l'automate puisque la tesselation a changé. Une configuration initiale évoluera différemment selon que l'on part à l'étape 0 ou à l'étape 1. Une configuration n'a de sens qu'avec sa tesselation.
|
|
|
|
De la même façon un décalage dans le temps d'un nombre impair modifie le comportement de l'automate puisque la tesselation a changé. Une configuration initiale évoluera différemment selon que l'on part à l'étape 0 ou à l'étape 1. Une configuration n'a de sens qu'avec sa tesselation.
|
|
|
|
|
|
|
|
L'isotropie est également généralement absente, en effet, le comportement variera si l'on effectue des rotations à 90°, sauf si la fonction de changement de bloc est invariante sous cette transformation.
|
|
|
|
|
| ... | ... | @@ -277,7 +306,7 @@ of Self-Reproducing Automata**, 1966. [^3] |
|
|
|
|
|
|
|
À la fin des années 40 et au début des années 1950, von Neumann s'est intéressé au problème des machines auto-réplicatrices et comme nous l'avons signalé dans la partie introductive de ce chapitre Stanislas Ulam lui proposa de simplifier le problème en étudiant cela dans un monde élémentaire, celui des automates.
|
|
|
|
|
|
|
|
Von Neumann a tout d'abord proposé un modèle de machine (le kinematon) capable de s'autorépliquer à partir de matériaux présents dans l'environnement et en utilisant un programme.
|
|
|
|
Von Neumann a tout d'abord proposé un modèle de machine (le kinematon) capable de s'autorépliquer à partir de matériaux présents dans l'environnement et en utilisant un programme.
|
|
|
|
Le kinematon (la machine) contient une auto-description que la machine interprète comme un programme mais constitue également un composant. Cette description est donc d'abord utilisée pour construire le réplicat et ensuite copiée pour que ce dernier contienne une auto-description.
|
|
|
|
|
|
|
|
Il est intéressant de préciser que cette description a été proposée avant la découverte de l'ADN et son mécanisme de réplication.
|
| ... | ... | @@ -288,8 +317,8 @@ C'es ensuite que von Neumann sur les conseils d'Ulam a proposé un automate cell |
|
|
|
> En axiomatisant les automates [autoréplicateurs] de cette manière, on (...) s'est résigné à ne pas expliquer comment ces éléments sont constitués de choses réelles, particulièrement comment ces éléments sont constitués de particules élémentaires ou même de molécules (...) on considérera simplement que des particules élémentaires dotées de certaines propriétés existent. La question à laquelle on espère répondre, ou au moins examiner, est : quels principes sont mis en œuvre dans l'organisation de ces molécules
|
|
|
|
dans les êtres vivants fonctionnels (...) [^3]
|
|
|
|
|
|
|
|
L'automate d'origine comporte 29 états et utilise un voisinage de 5 cellules. Chaque cellule est un automate à états finis. La taille de l'automate est de l'ordre de
|
|
|
|
200 000 cellules. Ces 29 états pour simuler des fils et le transport des signaux. Un enregistrement formé par une succession de cellules encode une suite d'actions que la structure doit effectuer. À l'aide d'une tête d'écriture, cette structure peut créer de nouvelles cellules, permettant ainsi une réplication d'elle-même et de l'enregistrement. Le modèle n'était que théorique. Ce n'est qu'en 1995 qu'une configuration fonctionnelle a été proposée par Renato Nobili et Umberto Pesavento[^4]. En 1968, Edgar F. Codd simplifia largement l'automate en utilisant 8 états.
|
|
|
|
L'automate d'origine comporte 29 états et utilise un voisinage de 5 cellules. Chaque cellule est un automate à états finis. La taille de l'automate est de l'ordre de
|
|
|
|
200 000 cellules. Ces 29 états pour simuler des fils et le transport des signaux. Un enregistrement formé par une succession de cellules encode une suite d'actions que la structure doit effectuer. À l'aide d'une tête d'écriture, cette structure peut créer de nouvelles cellules, permettant ainsi une réplication d'elle-même et de l'enregistrement. Le modèle n'était que théorique. Ce n'est qu'en 1995 qu'une configuration fonctionnelle a été proposée par Renato Nobili et Umberto Pesavento[^4]. En 1968, Edgar F. Codd simplifia largement l'automate en utilisant 8 états.
|
|
|
|
|
|
|
|
Avant de nous intéresser à la boucle de Langton, revenons sur le jeu de la vie ou l'un de ses dérivés. HighLife a été proposé en 1994 par Nathan Thompson. L'intérêt d'HighLife est qu'il existe une structure "simple" capable de se répliquer à l'identique
|
|
|
|
|
| ... | ... | @@ -300,7 +329,7 @@ Ces règles sont très proches de celles du jeu de la vie (seule la condition de |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pour terminer sur ce sujet il nous faut évoquer la configuration Gemini du jeux de la vie.
|
|
|
|
Pour terminer sur ce sujet il nous faut évoquer la configuration Gemini du jeux de la vie.
|
|
|
|
C'est un vaisseau qui se déplace de façon oblique il a été proposé par Andrew J. Wade en 2010. Il se déplace de 5120 cellules verticalement et de 1024 cellules horizontalement toutes les 33 699 586 générations. En avançant, cette structure crée une copie d'elle-même en détruisant la précédente.
|
|
|
|
|
|
|
|
|
| ... | ... | @@ -308,7 +337,7 @@ C'est un vaisseau qui se déplace de façon oblique il a été proposé par Andr |
|
|
|
|
|
|
|
### La boucle de Langton
|
|
|
|
|
|
|
|
L'idée de von Neumann était très ambitieuse dans sa volonté de réaliser un système universel pour lequel l'auto-réplication est vue comme une condition nécessaire du mécanisme de construction qu'il peut réaliser. La complexité de l'automate qui en a découlé a poussé d'autres chercheurs a tenter de le simplifier. Ainsi Codd a proposé un [automate](https://en.wikipedia.org/wiki/Codd%27s_cellular_automaton) à 8 états en 1968 mais comportant 283 126 588 cellules.
|
|
|
|
L'idée de von Neumann était très ambitieuse dans sa volonté de réaliser un système universel pour lequel l'auto-réplication est vue comme une condition nécessaire du mécanisme de construction qu'il peut réaliser. La complexité de l'automate qui en a découlé a poussé d'autres chercheurs a tenter de le simplifier. Ainsi Codd a proposé un [automate](https://en.wikipedia.org/wiki/Codd%27s_cellular_automaton) à 8 états en 1968 mais comportant 283 126 588 cellules.
|
|
|
|
|
|
|
|
|
|
|
|
À la fin des années 1970, Christopher Langton a pris le problème dans l'autre sens en tentant de définir un automate cellulaire le plus simple possible ayant certes perdu le caractère d'universalité mais étant capable uniquement d'auto-réplication, forme de condition suffisante. Il s'est inspiré de l'émetteur périodique de Codd qui est constitué d'une suite de cellule formant un signal, le tout entouré par une membrane. On pourra y voir, en passant, des liens avec la vision de Varela. Langton a donc conçu un automate cellulaire comportant une structure dont les composants constituent l'information nécessaire à sa propre réplication. Si, Von Neumann, Codd dans leurs propositions utilisent une tête de lecture en quelque sorte, la encore une analogie se dégage avec la machine de Turing, Langton lui s'en affranchit. La description de la boucle de Langton est simple :
|
| ... | ... | @@ -331,7 +360,7 @@ L'idée de von Neumann était très ambitieuse dans sa volonté de réaliser un |
|
|
|
```
|
|
|
|
|
|
|
|
* la membrane est formée des cellules dans l'état 2 ;
|
|
|
|
* les cellules internes contiennent l'information de réplication
|
|
|
|
* les cellules internes contiennent l'information de réplication
|
|
|
|
- Les séquences 7-0 et 4-0 se propagent vers la queue ;
|
|
|
|
- les séquences 7-0 prolongent la queue ;
|
|
|
|
- les séquences 4-0 construisent un angle droit vers la gauche.
|
| ... | ... | @@ -370,7 +399,7 @@ L'automate de Langton et ses améliorations comme celle proposée par [Byl](http |
|
|
|
|
|
|
|
> **Densité** : elle est mesurée par rapport à un état de chaque cellule, c'est donc le nombre de cellules d'un état donné sur le nombre total de cellules.
|
|
|
|
|
|
|
|
> **Synchrone** : l'évolution d'un automate est synchrone lorsque chaque cellule de l’automate est mise à jour à chaque itération.
|
|
|
|
> **Synchrone** : l'évolution d'un automate est synchrone lorsque chaque cellule de l’automate est mise à jour à chaque itération.
|
|
|
|
|
|
|
|
> **Asynchrone** : une ou plusieurs cellules sont mises à jour mais pas la totalité lors d'une itération.
|
|
|
|
|
| ... | ... | @@ -385,7 +414,7 @@ est mise à jour. Il existe deux types d’asynchronisme total : (1) _à mémoir |
|
|
|
|
|
|
|
> **Réplication** : un système est réplicateur s’il génère des entités identiques entre elles, mais différentes du système lui-même.
|
|
|
|
|
|
|
|
> **Copie** : il y a copie quand un système génère des entités à lui-même.
|
|
|
|
> **Copie** : il y a copie quand un système génère des entités à lui-même.
|
|
|
|
|
|
|
|
> **Autoreproduction** : "lorsque par un processus couplé à son propre processus de production une unité en produit une autre dotée d’une
|
|
|
|
organisation semblable à la sienne" (Varela). L’autoproduction est vue comme un moment
|
| ... | ... | @@ -396,12 +425,12 @@ de l’autopoïese. Cette liaison entre le processus de fonctionnement et le mé |
|
|
|
|
|
|
|
---
|
|
|
|
|
|
|
|
# Notes et références
|
|
|
|
# Notes et références
|
|
|
|
|
|
|
|
[^1]: S. Wolfram. (2002) _A new kind of science_. Champaign, IL: Wolfram Media
|
|
|
|
[^1]: S. Wolfram. (2002) _A new kind of science_. Champaign, IL: Wolfram Media
|
|
|
|
|
|
|
|
[^2]: On considérera ici que les vaisseaux étudiés se déplacent soit horizontalement, soit verticalement, soit en diagonale. Le premier vaisseau Gemini ayant un déplacement différent n’a en effet été découvert qu’en 2010, et il contient 846278 cellules...
|
|
|
|
|
|
|
|
[^3]: J. Von Neumann et Burks. (1996) _Theory of self-reproducing automata_. University of Illinois Press Urbana
|
|
|
|
[^3]: J. Von Neumann et Burks. (1996) _Theory of self-reproducing automata_. University of Illinois Press Urbana
|
|
|
|
|
|
|
|
[^4]: Pesavento U. (1995) An implementation of von Neumann’s self-reproducing machine. _Artificial Life_, 2(4), 337‑354. |
|
|
|
[^4]: Pesavento U. (1995) An implementation of von Neumann’s self-reproducing machine. _Artificial Life_, 2(4), 337‑354. |
