Automate cellulaire
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, le comportement global qui apparaît dans l'évolution d'une population de cellules peut s'avérer très complexe.
Chaos
Parmi les multiples notions tentant de cerner cette idée de complexité, la sensibilité aux conditions initiales, les transitivités, les expansivités des automates cellulaires semblent encore receler des mystères, notamment dans la possibilité d'automatiser ou non la reconnaissance de ces propriétés à partir de la règle locale.
Comportement asymptotique
Le fait d'exécuter en parallèle le même programme permet parfois de déduire des propriétés globales directement des propriétés locales. La topologie de Cantor permet d'exprimer cela autrement: des comportements asymptotiques particuliers ne peuvent se produire qu'en temps fini, comme la nilpotence des cellules. Une question qui en découle concerne les liens entre l'ensemble des configurations pouvant être atteintes en temps arbitrairement long et l'ensemble des valeurs d'adhérence d'orbites.
Décidabilité
Outre les propriétés topologiques, on peut essayer de comprendre la complexité de l'évolution du système en terme de prédictibilité. Dans quels cas saurait-on prévoir algorithmiquement où va aller la trajectoire d'un ensemble donné de configurations?
Simulations
Mais un automate cellulaire peut être vu lui-même comme un
modèle de calcul: il peut accomplir un procédé
algorithmique, et même simuler un autre système, dont il
contiendra d'une certaine façon la dynamique. Le fait de
contenir de nombreuses dynamiques différentes peut être vu
comme un signe de complexité.
Dynamique directionnelle
Les notions topologiques relatives à la complexité présentent
le problème que l'automate cellulaire accomplissant un simple décalage des états de ses cellules est considéré comme chaotique. Une solution à ce problème est d'étudier l'automate cellulaire
à composition par le décalage près. Il en ressort de nouvelles classifications permettant de mieux comprendre l'action de la règle locale elle-même.
Restrictions
Que deviennent les classifications tentant de capturer les différents comportements des automates cellulaires, lorsqu'on se limite à un certain sous-ensemble de départ (un sous-décalage)? Par exemple, les
automates de sable sont une restriction intéressante, qui se situe entre les automates cellulaires de dimension 1 et 2.
Trace
Une trace de l'automate cellulaire est le mot infini représentant l'évolution d'une cellule particulière. L'ensemble des traces d'un automate cellulaire est un sous-décalage, c'est à dire un ensemble de mots infinis qui peut être caractérisé par un ensemble de facteurs finis interdits. Sa dynamique est directement liée à celle de l'automate cellulaire, car avancer d'une lettre dans la lecture de la trace correspond à appliquer une étape d'évolution dans l'automate. Étant donné un sous-décalage particulier, il n'est pas évident de savoir s'il est l'ensemble des traces d'un automate cellulaire. Inversement, la plupart des propriétés des traces sont indécidables.
