Ensembles limite d’automates cellulaires

Les automates cellulaires (AC) servent souvent de modèles de systèmes dynamiques discrets ou comme modèles de calcul et constituent un système complexe: Une définition locale simple mais un comportement global difficile à prédire.

Nous nous intéresserons ainsi à leur comportement à long terme: Les états du système atteignables arbitrairement tard lors de leur évolution, c’est à dire l’ensemble limite de l’automate cellulaire. Si un AC atteint son ensemble limite au bout d’un temps fini il est dit “stable”, dans le cas contraire il est dit “instable”. Nous montrerons brièvement comment, en collaboration avec Pierre Guillon et Jarkko Kari, nous avons obtenu le premier exemple d’ensemble limite atteignable à la fois par un AC stable et un (autre) AC instable. Ce résultat a donné lieu à une conjecture sur une possible caractérisation des ensembles limite d’ACs stables. Par la suite nous montrerons que les ensembles limite ayant la propriété conjecturée nécessaire correspondent aux ensembles limite d’un certain type d’automates cellulaires stables. Le problème de savoir si tous les ensembles limite d’AC stables peuvent être atteints par ces ACs stables particuliers reste cependant ouvert.