Un automate cellulaire est un modèle de calcul parallèle synchrone, qui
consiste en une juxtaposition d'automates d'état fini (cellules) dont
l'état évolue dans le temps en fonction de celui de leurs voisins.
Malgré la simplicité de cette règle locale d'évolution, le comportement
global qui apparaît dans l'évolution d'une population de cellules peut
s'avérer très complexe. Il peut être relié à la dynamique symbolique
notamment par la trace, c'est à dire la succession des états d'une
cellule particulière, qui forme un sous-shift et peut avoir des
propriétés intéressantes.