À la découverte des automates cellulaires

John von Neumann (1903-1957), mathématicien américain d’origine hongroise. Institute for Advanced Study Archives / Photo © Alan Richards

Tout d’abord pensée en termes techniques, la machine auto-reproductrice de von Neumann est conçue pour puiser des pièces dans un bac de composants simples. Il suffit de monter ces composants ensemble de manière à former une machine identique à elle-même, puis de mettre en marche cette machine-fille. Très vite, ce projet apparaît trop ambitieux et sur une suggestion de son collègue Stanislaw Marcin Ulam (mathématicien américain d’origine polonaise), von Neumann décide alors d’examiner la question dans un espace mathématique simple qui serait une métaphore du monde réel. Cet espace est divisé en une grille pavée de cellules et chaque cellule a un état qui est choisi dans un ensemble fini d’états possibles. L’évolution des états des cellules se fait à temps réguliers : on suppose qu’une horloge donne à chaque pas de temps un signal de mise à jour. Ces changements obéissent à une loi dite locale, c’est-à-dire que chaque cellule met à jour son état en fonction de ce qu’elle « perçoit » de son voisinage. En l’occurrence, dans le modèle de von Neumann, cette perception d’une cellule est limitée à son propre état et à celui des quatre cellules adjacentes (Nord, Sud, Est, Ouest).

Grâce à son modèle mathématique qu’il appelle d’abord tesselation automata (automate sur pavage) puis cellular automata (automate cellulaire), von Neumann va montrer que l’on peut construire une machine auto-reproductrice tout en garantissant la non-trivialité de cette auto-reproduction. En effet, il démontre que l’univers des automates cellulaires, aussi simple soit-il, permet de simuler le déroulement de toute machine dont le fonctionnement est spécifié sans ambiguïté. Techniquement parlant, il montre que l’on peut inclure dans cet univers une machine de Turing universelle ce qui, moyennant une hypothèse aux fortes implications épistémologiques — il s’agit là de la thèse de Church —, revient à pouvoir simuler le déroulement de n’importe quel algorithme.

Le Jeu de la vie

De nos jours, on ne peut toujours pas admirer la construction de von Neumann. Celle-ci est en effet d’une complexité telle qu’une simulation effective du modèle prendrait trop de temps à être réalisée. A contrario, le modèle dit du Jeu de la vie, proposé par le mathématicien britannique John Horton Conway en 1970 est d’une simplicité désarmante. On considère des cellules réparties sur une grille mais celles-ci ont un état binaire : elles sont soit mortes, soit vivantes. La règle de transition locale se décline en deux sous règles, qui dépendent du nombre de voisins vivants parmi les huit cellules adjacentes (Nord, Sud, Est, Ouest ainsi que les cellules diagonales) :

(a) La règle de naissance stipule qu’une cellule passe de l’état mort à l’état vivant si elle est entourée de trois cellules vivantes.

La cellule au centre de la grille (en blanc cerclé de rouge) passe de l’état mort (blanc) à celui de vivant (gris) au temps T+1 car elle est entourée de trois cellules vivantes.

(b) La règle de survie stipule qu’une cellule vivante reste vivante à condition d’être entourée de deux ou trois cellules vivantes, autrement, elle passe à l’état mort.

La cellule grise au centre de la grille est vivante au temps T et elle le restera au temps T+1 car elle est toujours entourée de deux cellulles vivantes.

Initialement proposé comme un simple jeu, ce modèle déclencha un fort enthousiasme parmi les premiers aficionados de la programmation : en effet, en dépit de la simplicité des règles, les simulations informatiques permettaient d’observer des phénomènes surprenants dont les traits marquants peuvent se résumer à trois notions intuitives : l’auto-organisation, l’émergence et une évolution imprévisible du système.

Évolution du modèle du Jeu de la vie sur une grille de 50×50 cellules.
Les cases blanches et bleues représentent respectivement les cellules à l’état 0 et 1. La configuration initiale est choisie aléatoirement. L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

L’auto-organisation apparaît lorsqu’on observe l’évolution du Jeu de la vie partant d’un état initial aléatoire où chaque cellule a une chance égale d’être dans l’état vivant ou mort. Au bout de quelques pas de temps, ou pour reprendre la terminologie consacrée, au bout de quelques générations, les simulations montrent que l’état du système a perdu son aspect aléatoire. Il comporte des zones totalement mortes, des îlots stables de cellules vivantes, alors que d’autres restent en évolution.

Plus surprenante encore est l’apparition des « glisseurs », ces figures qui se déplacent en diagonale à vitesse régulière. Comment se fait-il que de tels déplacements de figures soient possibles alors que les règles ne spécifient aucun comportement de ce type ? Un examen des glisseurs confirme qu’il s’agit presque d’une « coïncidence ». Le glisseur est en fait formé de quatre figures différentes se succédant dans le temps. La quatrième figure est identique à la première, à ceci près qu’elle s’est translatée d’une case ! Cet exemple illustre bien la propriété d’émergence : à un certain niveau d’observation, on voit apparaître des structures dont le comportement n’avait pas été explicitement spécifié au niveau de la règle locale de transition.

Les glisseurs sont ces figures qui se déplacent en diagonale à vitesse régulière.
L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

Évidemment, on pourrait être tenté de décrire le comportement global du système à l’aide d’équations mathématiques. Pour ce faire, on peut chercher à réitérer les observations du système un grand nombre de fois et à dégager des constantes. Mais d’une simulation à l’autre, on observe des gammes de comportement extrêmement variées. Dans le cas de grilles de 50×50 cellules par exemple, le système peut se stabiliser au bout de quelques centaines de générations, tout comme il peut évoluer durant des milliers de générations sans se stabiliser. Un observateur ayant une mémoire infinie et des capacités d’observations infinies, un démon de Laplace informatique en quelque sorte, serait bien sûr à même de prédire l’évolution de n’importe quelle configuration. Malheureusement, pour les observateurs limités que nous sommes, il paraît hors de portée de pouvoir prédire l’évolution du système à l’aide d’équations mathématiques. Cette difficulté à prédire l’évolution du système a d’ailleurs des justifications théoriques : dans le cas d’une grille infinie (cas théorique), on conjecture qu’aucune méthode ne permet de faire plus vite que la simulation.

Au-delà du Jeu de la vie, la règle de majorité

Ayant fait la découverte d’un automate cellulaire particulier par le biais du Jeu de la vie, on peut légitimement se demander si cet automate est l’exception ou la règle. Autrement dit, toutes les règles locales produisent-elles des comportements aussi riches ? Pour commencer l’exploration d’autres règles, examinons la règle dite de majorité :

Évolution du modèle de la majorité sur une grille de 50×50 cellules.
Les cases blanches et bleues représentent respectivement les cellules à l’état 0 et 1. La configuration initiale est choisie aléatoirement. L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

Chaque cellule est dans un état binaire et prend l’état majoritairement présent dans son voisinage.

L’observation du système partant d’un état aléatoire révèle également une forme d’auto-organisation : on voit apparaître des régions uniformes qui ont tendance à devenir de plus en plus homogènes jusqu’à ce que se forment des îlots de cellules blanches dans des « mers » de cellules noires et vice-versa. Ensuite, les contours des « mers » et des « îlots » ont tendance à s’adoucir, c’est-à-dire à devenir plus lisses. À l’inverse du Jeu de la vie, ce processus est rapide : pour des grilles de 50×50 cellules, le système atteint un état stable au bout de quelques dizaines de générations seulement.

Peut-on là aussi parler d’émergence ? Étant donné que cette propriété n’est pas définie de manière formelle, il est difficile de donner une réponse tranchée. Quant aux possibilités de prédiction de l’évolution du système, elles se trouvent assez limitées dans la mesure où il n’existe pas d’outils propres aux automates cellulaires pour démontrer la règle de majorité. Il est toutefois possible d’utiliser des outils issus de la physique statistique pour démontrer les nombreuses propriétés (mathématiques, statistiques et dynamiques) de cette règle. Néanmoins, même pour un modèle aussi simple, la question de savoir comment prédire efficacement le temps de stabilisation à partir de la condition initiale reste encore non résolue à ce jour.

Le compteur de parité

Évolution du modèle du compteur de parité sur une grille de 50×50 cellules.
Les cases blanches et bleues représentent respectivement les cellules à l’état 0 et 1. La configuration initiale est choisie aléatoirement. L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

D’autres modèles comme le compteur de parité peuvent également être examinés. Ce modèle présente en effet des propriétés intéressantes. Il attribue aussi un état binaire aux cellules ; une règle stipule qu’au niveau local, chaque cellule compte le nombre de 1 dans son voisinage. Si le nombre total de 1 est pair, la cellule prend l’état 0 sinon, elle prend l’état 1. Là encore, il est difficile de dire a priori ce que donne cette règle lorsqu’on l’applique à une configuration initiale aléatoire. La simulation montre que, contrairement au modèle du Jeu de la vie et à la règle de majorité, le modèle du compteur de parité ne permet d’observer aucune forme d’auto-organisation. Partant d’une configuration aléatoire, le système reste aléatoire sans qu’il soit possible d’observer de stabilisation, même pour des temps de simulation très longs.

Pour autant, il ne faudrait pas en déduire que le modèle du compteur de parité est sans intérêt. Il illustre la propriété remarquable selon laquelle toute figure initiale s’auto-reproduit. Prenons par exemple la lettre N à l’état initial du système.

Évolution du modèle du compteur de parité sur une grille de 64×64 cellules.
La configuration initiale choisie est la lettre N. L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

Les simulations montrent que le système évolue de telle sorte que cette lettre N se duplique à l’infini, la seule limitation étant celle de la taille de la grille choisie. Pour se convaincre qu’une telle reproduction a lieu quelle que soit la figure initiale, on peut réitérer l’opération un grand nombre de fois avec des formes différentes, ou tout simplement, faire une analyse mathématique. On confirme ainsi que le système obéit à un principe de superposition et de duplication, ce qui explique pourquoi l’information initiale n’est jamais détruite. Cette propriété montre aussi pourquoi aucun ordre n’apparaît lorsque l’on part d’un état aléatoire : les nouveaux états obtenus sont une superposition d’états aléatoires.

La morale de l’histoire

Hormis l’aspect graphique ou ludique, quel est l’intérêt pour un scientifique d’étudier les automates cellulaires ? Les quelques exemples présentés dans cet article ont cherché à convaincre le lecteur qu’en dépit d’un fonctionnement local simple, la richesse de leurs comportements globaux avait de quoi surprendre ! Ceci peut avoir une implication forte sur notre compréhension des systèmes « naturels » : paradoxalement, l’étude des automates cellulaires semble dire que ce n’est pas parce qu’on a une connaissance parfaite des constituants d’un système que l’on comprend nécessairement comment se comporte l’ensemble. De même, l’observation de l’auto-organisation et de l’émergence suggèrent que l’on peut également obtenir des propriétés intéressantes d’un système sans qu’il soit nécessaire d’avoir un contrôle total de ses composants. C’est la raison pour laquelle les scientifiques essaient d’utiliser ces propriétés pour concevoir des systèmes électroniques ou informatiques d’un nouveau type. Les calculateurs actuels nécessitent des techniques de haute précision et ce, pour produire des circuits dans lesquels la position de chaque composant est décidée par avance. Or, les chercheurs pensent qu’en imitant la genèse des organismes vivants, des circuits évolués pourraient se former tout en laissant le système s’organiser avec une certaine autonomie.