Un automate cellulaire est un ensemble (fini) de cellules, toutes placées dans un espace (en général un plan). A tout instant, chaque cellule est caractérisée par un état. Quelque soit la cellule, toute cellule possède un voisinage (un ensemble de taille finie de cellules) et une fonction de transition. La fonction de transition permet de calculer le prochain état de la cellule à partir de son état courant et de l'état courant de toutes les cellules de son voisinage.
Le changement d'état des cellules d'un automate cellulaire est synchrone : toutes les cellules changent d'état en même temps. La configuration globale d'un automate permet de connaître l'état instantané de n'importe quelle cellule. La configuration locale d'une cellule C permet de consulter l'état de toutes les cellules au voisinage de la cellule C. La fonction de transition calcule donc un état à partir d'une configuration locale.
Exemple : le jeu de la vie est défini par un automate cellulaire dont les cellules sont situées sur un plan à coordonnées entières. Le voisinage d'une cellule est constitué des 8 cellules qui l'entourent ; une cellule ne possède que 2 états : vivante ou morte. La fonction de transition est définie ainsi :
Exemple : la simulation de la propagation d'un feu de forêt peut se modéliser ainsi : un automate cellulaire, dont les cellules sont situées sur un plan à coordonnées entières, modélise le terrain. Le voisinage d'une cellule est constitué des 8 cellules qui l'entourent ; une cellule possède 4 états : terre ou eau (ininflammable), bois non enflammé, ou bois en feu. La fonction de transition est définie ainsi :
Exemple : simulation du comportement d'une fourmi (puis d'une société de fourmis). Chaque cellule de l'automate correspond à une portion de terrain. Son état indique :
Quelques liens sur les automates cellulaires, ainsi qu'un sujet de TER de Maîtrise décrivant le type d'automate cellulaire à traiter.