Abonnez-vous

Les automates cellulaires de Wolfram

Michel Criton




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 y en a d'autres…

 

Parmi les automates cellulaires, certains (à une seule dimension) sont plus « simples » que d’autres. C’est le cas de l’automate de Wolfram, que l’on doit au mathématicien et physicien britannique Stephen Wolfram (né en 1959), connu pour avoir créé le logiciel Mathematica (Wolfram Research, 1988).

Les automates cellulaires sont des objets abstraits, des grilles constitués de « cellules » se trouvant chacune dans un état pouvant é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).
Le principe de l’automate de Wolfram est le suivant. On part d’une population initiale (l’étape 0) constitué de cellules vivantes disposées sur une ligne. Ensuite, à chaque étape, on applique systématiquement une même règle pour passer à l’étape suivante. Voici un exemple de règle :
 


 


À chaque étape, l’état d’une cellule C et de ses deux voisines va déterminer l’état de C (« vivante », en bleu, ou « morte », en blanc) à l’étape suivante. On peut définir ainsi 28 règles différentes.
Wolfram désigne chaque règle par son codage en notation binaire. Ainsi, la règle illustrée ci-dessus correspond à 01111110, c’est-à-dire à 126. Parmi ces 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, l’étape n + 1 comptant deux cellules vivantes de plus que l’étape n).
La règle 126 donne des résultats surprenants en partant d’une seule cellule vivante (la « graine ») car 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 ».

 

Le numéro complémentaire…



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 dans ce cas partir d’une population initiale « pleine » à l’exception d’une cellule morte. On obtiendrait ainsi, visuellement, l’exact négatif de l’image ci-dessus !
En fait, sur les deux cent cinquante-six règles possibles, on dénombre ainsi seulement quatre-vingt-huit règles fondamentalement différentes.

Quelle figure obtiendrait-on à partir d’une cellule vivante en appliquant la règle 118 ?




 

 

SOLUTION