... | ... | @@ -215,8 +215,12 @@ 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
|
|
|
|
|
|
On veut donc 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.
|
|
|
|
|
|
|
|
|
### L'automate réversible 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.
|
|
|
|
... | ... | @@ -228,18 +232,20 @@ Un automate réversible de bloc est composé de : |
|
|
* une règle de changement de partition après chaque pas de temps ;
|
|
|
* une règle de transition constituée d'une fonction qui prend en entrée une configuration d'états pour les cellules d'un même bloc et produit en sortie une autre affectation d'états pour les mêmes cellules.
|
|
|
|
|
|
À chaque pas de temps, la règle de transition est appliquée de façon synchrone à l'ensemble des blocs constituant la partition considérée et ensuite la règle de changement de partition est utilisée et le processus continu.
|
|
|
À chaque pas de temps, la règle de transition est appliquée de façon synchrone à l'ensemble des blocs constituant la partition considérée et ensuite la règle de changement de partition est utilisée et le processus continu. La partition de l'espace défini un voisinage.
|
|
|
|
|
|

|
|
|
|
|
|
Dans la représentation de l'espace ci-dessus un voisinage de Margolus est défini. La partition de l'espace alterne entre deux configurations de blocs (2 x 2) délimitées soit par le tracé rouge, soit par le tracé bleu. Cette tesselation particulière va nous être utile dans la suite, pour construire un automate réversible. Auparavant définissosn la notion de calcul réversible.
|
|
|
Dans la représentation de l'espace ci-dessus un voisinage de Margolus est défini. La partition de l'espace alterne entre deux configurations de blocs (2 x 2) délimitées soit par le tracé rouge, soit par le tracé bleu. Cette tesselation particulière va nous être utile dans la suite, pour construire un automate réversible. Auparavant définissons la notion de calcul réversible.
|
|
|
|
|
|
Un calcul informatique $`y = f(x)`$ est réversible, si la donnée d'entrée $`x`$ peut être retrouvée de façon unique à partir de $`y`$. Ainsi par exemple la négation en logique $`y = \neg x`$ est réversible. Si la sortie est 1 alors l'entrée est 0 et inversement. Par contre l'opérateur logique `ET` ne l'est pas puisque la sortie 0 correspond à trois différentes entrées : (0,0), (0,1), (1,0).
|
|
|
|
|
|
|
|
|
#### Automate cellulaire réversible
|
|
|
*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.
|
|
|
|
|
|
|
|
|
On veut donc 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.
|
|
|
|
|
|
|
|
|
## Automates auto-reproducteurs
|
... | ... | |