Automates cellulaires
- Bref aperçu des automates cellulaires élémentaires
- Mon horizon de travail
- Musique cellulaire.... à venir...
Bref aperçu des automates cellulaire élémentaires
Un automate cellulaire simple peut ce concevoir en une bande unidimensionnelle, celle-ci constituée de cellules à l'état 1 / 0 (représenté ci-dessous par des cellules noire / blanche ).
Pour faire fonctionné cet automate il faut bien sur lui donner des règles de conduites.
Nous allons donc dire a chaque cellules d'observer son voisin de gauche son état et son voisin de droite ce qui vas nous donnée une série de 8 formes d'observations possibles.
Chaque formes vas engendrer un comportement de la cellule (reste dans son état ou change d'état) au cycle suivant . Nous parlons ici de cycle parallèle, toute les cellules sont mis a jour a chaque cycle. ( il existe d'autre méthode dite : serie dans le quel une ou plusieurs cellules sont misent à jour ) .
Exemple d'application :
Enumération de la règle dite de "30" ( 00011110 en binaire équivaux à 30 en décimale).
| Observation | |
|||||||
|---|---|---|---|---|---|---|---|---|
| Comportement | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
La feuille de travail avec pour départ une cellule vivante "M"=1
| cellule |  |
|---|---|
| Etat cycle 1 |  |
Il nous faut nous placer dans chaque cellule et observer sont voisin de gauche, la cellule elle-même et son voisin de droite. Commençons plaçons-nous sur la cellule "B" le voisin de gauche "A"= 0, "B"= 0, le voisin de droite "C"= 0. Le résultat de l'observation est "000" et le comportement est "0". Au cycle 2 "B"=0
On continue
| cellule | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | ... |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Observation | 000 | 000 | 000 | 000 | 000 | 000 | 000 | 000 | 000 | 000 | 001 | 010 | 100 | 000 | 000 | ... |
| Comportement | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | ... |
Ce qui nous donne si nous continuons les itérations le résultat suivant
Et si on continue ....
Pour résumer il y a 256 automate élémentaire possible
23=8 formes d'observation possibles (2 correspond au nombre d'état que peut prendre la cellule et
3 corespond au nombre de cellules observés la cellule elle même et ces deux voisins.)
Et pour trouvé le nombre de règle possible
28=256 règles possibles, (2 correspond au nombre d'état que peut prendre la cellule et 8 corespond au nombre de forme d'observation)
| Observation | |
valeur décimale | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Comportement | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | =0 |
| Comportement | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | =1 |
| Comportement | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | =2 |
| Comportement | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | =3 |
| Comportement | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | =4 |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | |
| Comportement | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | =255 |
Mon horizon de travail
On voit très vite que le nombre de règles s'envolent littéralement en augmentent le nombre de cellule observées ou le nombre d'état
| 2 états | 3 états | 4 états | 5 états | |
| 2 cellules | 16 | 1.97E+004 | 4.29E+009 | 2.98E+017 |
| 3 cellules | 256 | 7.63E+012 | 3.40E+038 | 2.35E+087 |
| 4 cellules | 6.55E+004 | 4.43E+038 | 1.34E+154 | ... |
| 9 cellules | 1.34E+154 |
13407807929942600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Mon horizon de travail c'est porté sur des automates bidimensionnel a 2 états et 9 cellules observées sur les quelles sont basé de nombreux classiques. ces automates ont un nombres considérables de comportement, le nombre d'observation possible ce monte à 512, et sera codé sur 9 bit , le premier bit est attribué a la cellule courante et le second au coin haut de gauche. Le choix de cette numérotation est personnel .
Ce qui nous donne les poids suivant dans un espace "XY"
| Position | "x+1 y+1" | "x y+1" | "x-1 y+1" | "x+1 y" | "x-1 y" | "x+1 y-1" | "x y-1" | "x-1 y-1" | "x y" |
|---|---|---|---|---|---|---|---|---|---|
| numéro de la cellule | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| valeur décimale | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Exemple d'application :
| Position | "x+1 y+1" | "x y+1" | "x-1 y+1" | "x+1 y" | "x-1 y" | "x+1 y-1" | "x y-1" | "x-1 y-1" | "x y" | |
|---|---|---|---|---|---|---|---|---|---|---|
| numéro de la cellule | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| valeur décimale | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |
| Observation | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | Total |
| Résultat | 0 | 0 | 64 | 0 | 0 | 0 | 4 | 2 | 1 | 71 |
Cette numérotation vas nous permettre de concevoir et d'exploré l'ensemble des ~1.34E+154 règles possibles ...
Voici les 512 formes d'observation possible dans notre univers cellulaire avec un poids compris de 0 a 511
Prenons l'exemple du jeux de la vie de John Horton Conway en 1970 qui imagina les règles suivantes.
- Une cellule morte possédant exactement trois voisines vivantes devient vivante (elle naît).
- Une cellule vivante possédant deux ou trois voisines vivantes le reste, sinon elle meurt.
L'énoncé de cette règle est très simple mais regardons de plus près. La partie qui régule les cellules mortes 256 forme d'observation dont 56 vont faire un changement d'état "vivante" et 200 qui vont maintenir la cellule dans sont état "morte"
La deuxième partie de l'énoncé pourrait ce décrire aussi ainsi: les cellules vivante meurt si le nombre de voisin diffère de 2 ou 3 ce qui nous donne 177 forme d'observation font mourir la cellule 79 la conserve dans son état vivante
La suite bientôt ....