| ... | ... | @@ -218,8 +218,7 @@ Le jeu de la vie est irréversible. Il n'est pas possible de déterminer des rè |
|
|
|
|
|
|
|
La combinaison de structure permet de générer des structures qui génèrent elles-même d'autres structures. C'est le cas des canons dont la partie principale se répète périodiquement, comme un oscillateur, et qui émet des vaisseaux à intervalle régulier. Le plus connu est celui de Gosper.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dans le bestiaire du jeu de la vie ces structures ne sont pas anodines, elles permettent de répondre à une question que Conway s'était posé dès le début, la croissance peut-elle être infinie ? En effet, pour envisager construire une machine de Turing, il faut que cette condition soit respectée. Depuis cela a été [réalisé](https://www.youtube.com/watch?v=My8AsV7bA94). Plus amusant (?) encore, le jeu de la vie peut simuler le jeu de la vie !
|
|
|
|
|
| ... | ... | @@ -264,7 +263,7 @@ Un automate réversible de bloc est composé de : |
|
|
|
|
|
|
|
À 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éfinissons la notion de calcul réversible.
|
|
|
|
|
| ... | ... | @@ -294,9 +293,7 @@ Vous étudierez en particulier la rotation à 90°. Elle consiste en une règle |
|
|
|
|
|
|
|
Sur la rotation à 90° vous testerez les translations spatiales et temporelles et rechercherez des structures stables, périodiques et des vaisseaux.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
## Automates auto-réplicatifs
|
| ... | ... | @@ -304,7 +301,8 @@ Sur la rotation à 90° vous testerez les translations spatiales et temporelles |
|
|
|
> Les êtres vivants sont des agrégats compliqués de composants simples et, selon toute théorie probabiliste ou thermodynamique raisonnable, ils sont très improbables. La seule chose qui explique ou atténue ce miracle est le fait qu’ils se reproduisent : si, par accident, il en apparaît un seul, alors les principes des probabilités ne s’appliquent plus et il s’en produit beaucoup. *John von Neumann*, **Theory
|
|
|
|
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.
|
|
|
|
|
| ... | ... | @@ -324,17 +322,17 @@ L'automate d'origine comporte 29 états et utilise un voisinage de 5 cellules. C |
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Les règles sont les suivantes : une cellule morte naît à l'étape suivante si elle est entourée de 3 ou 6 voisines vivantes, une cellule vivante survit à l'étape suivante si elle est entourée de deux ou trois cellules vivantes.
|
|
|
|
Ces règles sont très proches de celles du jeu de la vie (seule la condition de naissance pour 6 cellules vivantes voisines diffère). Cet automate est néanmoins semble t-il moins riche.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Terminons ce paragraphe sur un clin d’œil.
|
|
|
|
|
| ... | ... | @@ -381,7 +379,7 @@ La séquence auto-réplicatrice est la suivante : |
|
|
|
```
|
|
|
|
Les 6 `7 0` allongent donc la queue et les 2 `4 - 0` construisent l'angle droit. Une règle bloque l'évolution quand il n'y a plus assez d'espace.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### Exercice
|
| ... | ... | |
| ... | ... | |
