Publicité
Choux romanesco, Vache qui rit et intégrales curvilignes
1 décembre 2007

De la vie jaillit le chaos

A l'origine, il y avait le Chaos. Dieu a ensuite inventé l'Univers, puis les mathématiciens, qui ont inventé le chaos...
Si le nez de Cléopatre eut été plus court, il est fort probable que la tour Eiffel n'existerait pas à l'heure actuelle. (En effet, elle ne se serait pas cogné dans une porte un matin de l'année -40, sa vie aurait été complètement décalée de 5 secondes, ce qui suffit à ne pas lui faire la même descendance, et ainsi de suite...). Ce qui est chaotique, c'est ce que l'on appelle communément "l'effet papillon" : une extrême sensibilité aux conditions initiales.

Mais en fait, je ne vais pas vraiment ici parler de chaos, mais simplement de la création remarquable de John Conway : le jeu de la vie !
(Même si le jeu de la vie n'est pas à proprement parler un jeu, puisqu'il n'y a pas vraiment besoin de joueurs, c'est plutôt quelque chose de contemplatif...)

C'est en fait un automate cellulaire, c'est à dire, une grille de "cellules" évoluant au cours du temps selon un petit nombre de règles.

Ici, on se place dans une grille simple, faite de carrés, chaque cellule est donc encadrée par 8 autres cellules. Chaque cellule ne peut avoir que deux état : la vie et la mort.
* Si une cellule en vie n'a qu'une voisine ou aucune, elle meurt de solitude.
* Si une cellule en vie a 4 voisines ou plus, elle meurt de surpopulation.
* Avec 2 ou 3 voisins, une cellule en vie reste en vie.
* Quand exactement 3 cellules vivantes encadrent une 4eme morte, celle-ci renaît à l'étape suivante.

Petit exemple :

jeu_de_la_vie_regles

Les cellules en vie sont les cercles (bleus, verts ou jaunes), les mortes sont les carrés noirs ou gris.
Les cellules bleues illustrent la première règle (0 ou 1 voisin)
Les jaunes illustrent la deuxième (4 voisins ou plus)
Les vertes illustrent la troisième (2 ou 3 voisins)
Les carrés gris illustrent la dernière règle (3 voisins exactement)

Le côté ludique du jeu de la vie est différent suivant les personnes qui s'y intéresse :
- Le matheux y cherchera les motifs particuliers qui reviennent souvent : structures stables, périodiques, etc.
- L'autre matheux cherchera les situations initiales engendrant les situations les plus chaotiques.
- Le psychopathe cherchera des situations initiales qui dessineront après une cinquantaine de générations la Joconde.
- L'artiste cherchera quant à lui à faire des choses artistiques (parce que c'est un artiste)

<Interlude publicitaire>
Pour jouer avec le jeu de la vie, vous pouvez utiliser l'applet présent sur ce site, sur lequel on peut également trouver tout un tas de logiciel simulant le jeu de la vie. Perso, j'ai utilisé Mirek's Cellebration, mais je ne saurais dire si c'est le meilleur.
</interlude publicitaire>

Le matheux
Créé en 1970, celà fait déjà 37 ans que de nombreux matheux s'intéressent à la puissante simplicité du jeu de la vie, et de nombreux motifs simples ont déjà pu être repérés.

o) Les structures stables
Les structures les plus facilement repérables sont les structures stables ; celles-ci n'évoluent pas au cours du temps, sauf si elles sont dérangées par d'autres cellules. La plus simple est le "bloc", un carré 2×2 de cellules, mais on en a tout une ribambelle :

stables

o) Les oscillateurs
Les oscillateurs, aliais structures périodiques, sont les structures qui reviennent à leur état initial après un certain nombre de génération. Ceux de période 1 sont les structures stables, on doit pouvoir trouver des oscillateurs pour n'importe quelle période (bien qu'on en ait pas encore trouvé de période 19, 23, 31, 37, 38, 41, 43 ou 53). Les oscillateurs les plus simples, de période 2, sont ceux-ci : à gauche, le clignotant, et à droite, le crapaud.

oscill

Pour la période 4, on peut trouver par exemple le trampoline (à gauche) ou l'horloge (à droite) :

oscill4

o) Les vaisseaux
Encoreplus fort que les oscillateurs, ce sont les vaisseaux ! Tout comme les oscillateurs, ils reviennent dans leur situation initiale après un certain nombre de génération, mais ils réapparaissent décalés par rapport à leur position initiale. Un vaisseau est de type A-B s'il se déplace après un certain nombre de génération de A cases horizontalement et B cases verticalement. Théoriquement, on peut trouver des vaisseaux pour A et B quelconques, mais dans la pratique, il n'y a que deux type de vaisseaux :
- Les vaisseaux diagonaux, qui se déplacent... diagonalement (avec A=±B). L'exemple le plus simple est le planeur (à gauche)
- Les vaisseaux transversaux, qui se déplacent verticalement ou horizontalement, comme le LWSS (Lightweight Spaceship - à droite)

vaisseaux

o) Les canons
Et encore plus fort que les vaisseaux... Ce sont les canons qui fabriquent des vaisseaux de manière périodique. On peut évidement imaginer des structures qui fabriqueraient des canons, ou bien, des canons se déplaçant comme des vaisseaux...

Gol_gun

L'autre matheux
Adepte du chaos, l'autre matheux s'amuse à chercher les plus petites structures qui ne se stabilisent qu'après un très grand nombre d'étapes (comme pour les histoires de castors affairtés, ce n'est pas intéressant si elles grandissent infiniement). Le plus difficile là-dedans, c'est qu'il est impossible de savoir ce qui se passera pour une structure avant de l'avoir essayé, le jeu de la vie ayant un comportement chaotique, donc imprévisible. Le bon motif à donner en exemple est le motif Acorn qui ne se stabilisera qu'après 5206 générations (et après avoir fabriqué 25 vaisseaux) :

Acorn

C'est bien de s'intéresser au futur d'un motif, mais on peut aussi s'intéresser à son passé. Toute structure a t'elle forcément un antécédent ? Une structure sans antécédent est appelé un "Jardin d'Éden", le premier à avoir été découvert est contenu dans un rectangle 33×9 (à gauche), le record actuel étant celui contenu dans un rectangle 13×12 (à droite) :

JdE1JdE2

Depuis, on cherche des jardins d'Éden plus petits encore, on ne peut pas encore dire s'il en existe ou pas. La seule chose que l'on sait, c'est qu'une structure contenue dans un rectangle 6×5 a forcément un prédécesseur...

Le psychopathe
De son côté, le psychopathe essaye de placer de manière adéquate des canons et des vaisseaux de manière à fabriquer des choses intéressantes. Par exemple, la structure suivante fabriquera à tour de rôle les nombre de 1 jusqu'à 9... (Si vous avez comme moi téléchargé MCell, le fichier est DecimalCounter.l)


psycho

L'artiste
Enfin, l'artiste s'amuse à fabriquer les plus jolis des vaisseaux !

artiste

L'informaticien théorique
Et je n'ai pas parlé de l'informaticien théorique, qui y voit la dedans des ET, des OU et des NON, ou qui y voit une machine de Turing universelle...


Sources :
Un peu trop de Wikipédia (J'aurai du penser plus tôt à dévaliser la BU...)

Publicité
Publicité
Commentaires
T
Ah mais en fait c'est passionnant, la structure qui écrit des chiffres est incroyable, et les jolis vaisseaux... jolis !
Répondre
M
Je suis un peu déçue, je reconnais pas la Joconde dans la vision du psychopathe... ;)
Répondre
T
Je reviendrais quand j'aurais plus de courage. Mon premier projet de première année de DUT info était de programmer un jeu de la vie. J'en garde un fort traumatisme ^^
Répondre
Publicité
Publicité