Les automates cellulaires de Wolfram

Les automates cellulaires sont aujourd’hui bien connus grâce au fameux « jeu de la vie » introduit par le mathématicien britannique John Horton Conway. Mais il en existe d’autres, notamment des automates à une seule dimension, plus « simples », comme l’automate de Wolfram.

Cet automate doit son nom au mathématicien et physicien britannique Stephen Wolfram, né en 1959, également connu pour avoir créé le logiciel Mathematica (Wolfram Research, 1988).

Un automate cellulaire est une grille de « cellules », chacune se trouvant dans un état susceptible d’évoluer au cours du temps. Le jeu de la vie en est l’exemple le plus fameux (voir Mathématiques et Informatique, Bibliothèque Tangente 52, 2014).

Pour l’automate de Wolfram, on part d’une population initiale de cellules vivantes disposées sur une ligne : il s’agit de l’étape 0. À chaque étape, on applique systématiquement la même règle pour obtenir l’étape suivante.

À chaque étape, l’état d’une cellule C, ainsi nommée, et celui de ses deux voisines déterminent l’état de C à l’étape suivante : « vivante » en bleu ou « morte » en blanc. On peut ainsi définir 2 8 règles différentes.

Wolfram désigne chaque règle par son codage en notation binaire. La règle illustrée ci-dessus correspond ainsi à 01111110, c’est-à-dire à 126.

Parmi les deux cent cinquante-six règles possibles, certaines ne présentent guère d’intérêt, comme la règle 0, dans laquelle une population quelconque meurt sans descendance, ou la règle 255, qui donne un triangle plein : si n désigne le numéro d’une étape, l’étape n + 1 compte deux cellules vivantes de plus que l’étape n.

La règle 126 donne des résultats surprenants lorsqu’on part d’une seule cellule vivante, appelée la « graine » : les étapes successives génèrent une figure connue sous le nom de triangle de Sierpinski.

Pour vous familiariser avec les automates cellulaires, vous pouvez tester cette règle avec une population initiale de plusieurs cellules vivantes, ou plusieurs « graines ».

On peut également définir une règle complémentaire d’une autre. Ainsi, la règle complémentaire de 01111110 (126) est la règle 10000001 (129). Il faudrait alors partir d’une population initiale « pleine », à l’exception d’une cellule morte : on obtiendrait visuellement l’exact négatif de l’image ci-dessus.

En fait, parmi les deux cent cinquante-six règles possibles, on ne dénombre que quatre-vingt-huit règles fondamentalement différentes.