Ecrivez-nous

automate cellulaire, réseau formé d’éléments simples, appelés cellules, connectés localement dans un espace à n dimensions.

Chaque cellule d’un automate cellulaire possède un nombre fixe de cellules dites voisines, avec lesquelles elle est en contact direct. Une cellule se trouve à un temps t donné dans un état appartenant à un ensemble fini d’états possibles. L’état d’une cellule à un temps t + 1 dépend uniquement de l’état au temps t et de celui des cellules voisines à ce même temps t, et est déterminé selon une fonction de transition. On appelle configuration de l’automate l’ensemble des états de toutes les cellules le composant. La configuration d’un automate cellulaire évolue donc au cours du temps à partir d’une configuration initiale et selon les fonctions de transition des cellules.

Les automates cellulaires ont été proposés par le mathématicien John von Neumann en 1966. Ils sont utilisés pour modéliser des systèmes réels : interactions entre particules, formation de galaxies, systèmes biologiques, etc. Il a été démontré que les automates cellulaires constituent une bonne alternative aux équations différentielles.

Le « jeu de la vie » est un cas particulier d’automate cellulaire proposé par Conway en 1970 : c’est un automate cellulaire bidimensionnel, à deux états possibles par cellule. Une cellule possède alors huit cellules voisines, et peut être active ou non à un temps donné. Les règles de transition des cellules sont les suivantes :

• une cellule ayant deux cellules voisines actives ne change pas d’état ;
• une cellule ayant trois cellules voisines actives devient active ;
• une cellule ayant une ou plus de trois cellules voisines actives devient inactive.

Le jeu de la vie permet d’obtenir des configurations stables, périodiques ou non. Conway a prouvé en 1982 que le jeu de la vie est un moyen universel de calcul, au même titre que les machines de Turing.