Métacellules : vers l'infini et au-delà...
Origines
"Blinkers"
Jardins d'Éden
Navires
Canons...
"Breeders"
Machines
Métacellules
Métacellules
Autosimilarité
Merci Golly
Et après
Questions ouvertes
Recherches futures
Documents
Métacellules
Récemment (2009) on a mis au point une métacellule. Il s'agit d'une configuration de forme carrée (2048×2048 cases). Sa population peut varier de 20 000 cellules (lorsqu'elle est "vide" -- on ne distingue alors que son "cadre") à 60 000 cellules, quand elle est "pleine".Dans ce dernier cas, les cases ne sont pas toutes occupées [1], loin de là, mais parcourues par des trains de navires Cela donne à la métacellule un aspect hachuré : à petite échelle, la métacellule apparaît noire.
L'exploit réside dans le fonctionnement des métacellules, qui reproduit exactement celui des cellules élémentaires ! Une métacellule "vivante" (hachurée) ayant deux ou trois voisines dans le même état "survit", sinon elle "meurt" (elle devient vide, transparente). Une métacellule vide voisine de trois métacellules vivantes enregistre une naissance : elle passe à l'état hachuré.
Il faut le voir pour le croire : la configuration suivante (appelée une métagalaxie [2]), de 15×15 métacellules, comporte 7 488 195 cellules élémentaires.
la métagalaxie entière
une métacellule
le coin d'une métacellule
détail montrant les trains de navires
Autosimilarité
L'existence des métacellules introduit l'autosimilarité au cœur du Jeu de la vie, décidément bien nommé. On imagine la suite : méta-métacellules, méta-méta-méta...Mais la performance ne s'arrête pas là. La métacellule est programmable ! Elle peut, nous l'avons dit, mimer les règles du Jeu de la vie. Mais il est aussi possible de la configurer pour respecter n'importe quel ensemble de règles utilisant le voisinage standard de huit cases.
Ainsi, ce n'est pas seulement le Jeu de la vie qui se trouve représenté à l'intérieur de lui-même, mais n'importe quel automate cellulaire utilisant la même topologie !
Merci Golly
Quel programme est capable de manier des configurations aussi monstrueuses ? Le programme libre Golly intègre l'algorithme Hashlife, dont les bases datent de 1984 [3]. Le développement a repris en 2004 sous l'impulsion de T. Rokicki [4]. Hashlife recherche des régularités dans les configurations qu'il traite, mémorisant des configurations partielles pour ne pas avoir à les recalculer. Hashlife utilise massivement la récursivité, ce qui le rend très gourmand en mémoire. Il accélère au fur et à mesure de ses calculs [5], groupant les générations par puissances de 8.Dans le cas de la métagalaxie ci-dessus, après un démarrage progressif, on voit la configuration évoluer à une vitesse folle grâce à Golly, au point de ne plus parvenir à suivre les modifications des métacellules ! En 30s, la génération 1055 est atteinte. Il faut ralentir Golly pour observer, par "zooms" successifs, le détail de ce qui se passe...
Golly illustre à merveille la supériorité de l'analyse mathématique sur la programmation naïve et irréfléchie. Jamais un programme de type "force brute" ne pourra approcher ses performances.
Et après ?
Questions ouvertes
Il reste de nombreux points non résolus, malgré tous les progrès effectués. Pour certains, l'étude théorique a donné un résultat d'existence non constructif : la réalisation explicite reste à faire. Citons :- la résolution complète des période des blinkers, ou des vitesses des navires ;
- la construction d'une population qui se duplique effectivement ;
- la synthèse au moyen de glisseurs de toute configuration stable, et plus généralement de toute configuration qui ne soit pas un jardin d'Éden, et la création d'une machine réalisant cette synthèse, etc.
Recherches futures
Les performances des algorithmes de type Hashlife ont donné un nouvel essor à l'étude des automates cellulaires. Grâce à eux, on accède à des niveaux de complexité et de richesse insoupçonnés.Le Jeu de la vie suscite un regain d'intérêt chez certains philosophes. Jusqu'à quel point mérite-t-il son nom ? J. H. Conway et R. K. Guy n'ont pas hésité à déclarer :
<< Il est probable qu'en remplissant une partie assez grande du plan infini du jeu de la vie par une configuration aléatoire, alors, après un long moment, émergeront des êtres autoreproducteurs qui peupleront l'espace. >>
Notes
[1] (la population s'éteindrait en une génération)[2] On l'appelle ainsi car elle modélise à grande échelle la galaxie de Kok, un classique blinker de période 8 :
.[3] W. Gosper, toujours lui !
[4] également bien connu des utilisateurs de (La)TeX pour le programme d'impression Postscript dvips
[5] pour peu que l'on active son mode hyperspeed