Résumé : En partant du hasard on obtient en plusieurs phases successives d’étranges cristallisations qui ressemblent à une forme de vie primitive. Un automate cellulaire, système mathématique très simples à décrire, permet d’observer des images d’une complexité stupéfiante.

Mots-clés :Automate cellulaire, cristallisation, spirale, probabilité.

Solutions :

La solution actuellement proposée est donnée en P5JS.

thèmes

de plus

La formation des cristaux
 

L’exercice s’inspire de l'article Cristallisation en spirale de A. Dewdney, Pour la science No 144,octobre 1989.

A. Dewdney commence son article, sous-titré Un univers de débris, de mosaïques, de défauts et de démons en déclarant que certains systèmes mathématiques, très simple à décrire, engendrent des univers miniatures d’une incroyable complexité. Ces univers sont inaccessibles aux télescopes et aux fusées, il ne peuvent apparaître que sur des écrans d’ordinateurs.

Les automates cellulaires sont très spectaculaires : comme l’univers qui nous entoure, ils évoluent sans cesse et se développent parfois comme des cristallisations. Celui inventé par David Griffeath, de l’Université de Madison, fournit un des meilleurs univers miniatures.

Initialement dans une configuration aléatoire, il se développe en quatre phases successives et s’emplit finalement d’étranges cristallisations qui ressemblent à une forme de vie primitive.

Un automate cellulaire est un réseau illimité dont chaque case ou cellule, peut se trouver dans divers états. Une horloge règle l’évolution : à chaque cycle d’horloge, les cellules changent d’état conformément à quelques règles simples. Sur un ordinateur, les cellules sont représentées par les points de l’écran, et les états par des couleurs. Une fois définies les règles d’évolution des cellules et leur configuration initiale, un automate informatique engendre d’extraordinaires motifs colorés, qui se modifient avec le temps.

L’invention de D. Griffeath, que A. Dewdney appelle l’espace cyclique, provient d’une idée très simple. Il engendre des phénomènes superbes, très intéressants d’un point de vue scientifique. La règle de base est la suivante: pour chaque cellule, n états sont possibles et numérotés de 0 à n - 1. A chaque cycle, une cellule dans l’état k « mange » les cellules adjacentes qui sont dans l’état k - 1, et passent ainsi de l’état k - 1 à l’état k. Cela ressemble à une chaîne alimentaire: une cellule dans l’état 2 mange une cellule dans l’état 1, même si cette dernière mange, au même instant, une cellule dans l’état 0. Toutefois, dans l’espace cyclique cette chaîne est sans fin, car les cellules dans l’état 0 mangent les cellules voisines dans l’état n - 1.


Par l’application de cette seule règle simple, l’espace cyclique peut transformer une répartition aléatoire de points colorés en des spirales anguleuses et stables. La phase correspondante à la configuration initiale est celle des débris ; progressivement, ces débris laissent place à des gouttes de couleurs ; celles-ci grossissent et, à mesure que les débris disparaissent, envahissent tout l’espace. C’est alors que naissent des spirales cristallines qui s’étendent en tournoyant.

Chaque spirale prend naissance à partir d’un « défaut », terme que D. Griffeath emprunte à la cristallographie. La croissance est lente et majestueuse, mais les spirales finissent par manquer de place. Certaines sont absorbées, tandis que d’autres persistent et dominent le dernier stade de l’espace cyclique : elles forment les « démons ».

Quel que soit le nombre d’états possibles, le scénario est toujours le même : les débris se transforment en gouttes, cèdent la place aux défauts, puis aux démons. Les trois premières phases sont métastables : elles persistent longtemps avant que la dernière phase s’établisse.

Pourquoi une répartition initiale d’états, aléatoire, est-elle métastable? Autrement dit, pourquoi faut-il si longtemps pour que les plages de l’écran perdent leur aspect poivre et sel ? Quelques gouttes colorées se forment parfois, momentanément, dès le début de la génération, mais elles paraissent sans importance, car elles ne semblent pas se développer.

On comprend facilement l’origine de la métastabilité. Supposons qu’une cellule soit dans l’état 5 ; quelle est la probabilité qu’au moins une de ses quatre voisines soit dans l’état 4? Elle est faible: si les cellules peuvent se trouver dans 20 états différents, la probabilité est égale à 0,19. Même si l’une des cellules voisines constitue une nourriture acceptable, quelle est la probabilité que la cellule initiale ou la cellule absorbée, se trouve à côté d’une cellule dans l’état 4, au cycle suivant? En poursuivant ce raisonnement probabiliste, on comprend ce qui se passe sur l’écran lorsque l’espace cyclique évolue à partir d’une configuration aléatoire: même au bout de quelques cycles d’absorptions sporadiques, l’espace cyclique stagne à l’état de débris inorganisé.

Toutefois, il n’est absolument pas inerte : souvenons-nous des gouttes isolées! En partant de leurs bords, des vagues d’absorption se propagent et rebondissent sur les débris avoisinants. Non seulement cette activité semble préserver les gouttes, mais encore, elle permet leur développement: des cellules provenant des débris environnants sont progressivement incorporées aux gouttes. Puis en grossissant, ces gouttes finissent par se rejoindre, n’épargnant que quelques débris: c’est la phase mosaïque. Pourquoi les gouttes se développent-elles?

La présence de boucles est l’une des raisons de cette croissance continue. Une boucle est une chaîne fermée de cellules telle que l’état de chaque cellule diffère d’au plus une unité de l’état de la cellule suivante. On obtient l’état de chaque cellule de la boucle en ajoutant -1, 0 ou 1 à l’état de la cellule voisine (n’oublions pas que dans l’espace cyclique, l’état 0 ne diffère que d’une unité de l’état maximal n). La somme des différences pour toute la boucle n’est pas nécessairement nulle, et les boucles pour lesquelles cette somme de différences n’est pas nulle assurent une croissance infinie de la goutte. Ce sont ces « défauts » qui engendrent la troisième phase de l’espace cyclique.

Les boucles de type « défaut » ont des actions différentes des autres boucles : elles obligent les cellules environnantes à changer d’état à un rythme régulier. Sur l’écran, la région entourant un défaut forme une spirale et, à la longue, c’est tout l’espace cyclique qui se remplit de spirales colorées en croissance.

Comment ces défauts se forment-ils à partir des « débris »? Naturellement certains défauts sont parfois présents dès la première configuration de l’univers cellulaire: dans un espace illimité, il en existe même certainement. Cependant des défauts se forment également à des endroits où ils étaient absents. Comment? Selon D. Griffeath, certains défauts sont plus «efficaces» que d’autres, car ils se comportent comme des horloges à n états: les états des cellules défilent exactement en n cycles d’horloge le long de la plus petite boucle. Les spirales qui évoluent lentement sont absorbées par les plus rapides, et les démons qui peuplent la quatrième phase de l’espace cyclique règnent en maîtres, séparés les uns des autres par des bannières invisibles, mais immuables.

Indications

Pour construire un programme de simulation de l’espace cyclique, on peut conseiller l’algorithme suivant : on utilise deux tableaux qui enregistrent deux configurations successives de cellules.

A chaque étape on vérifie l’état des quatre cellules adjacentes: si l’une des cellules voisines a un état supérieur d’une unité à celui de la cellule, cette dernière sera «absorbée», son état augmentant d’une unité.

Les sommes sont calculées modulo n. Les indices sont calculés modulo le nombre de lignes et/ou colonnes.

Version p5.js. Instructions: faire reset pour une autre configuration aléatoire.