Problèmes de stabilité pour les automates cellulaires probabilistes

par Hugo Marsan (Université Toulouse III - Paul Sabatier)

mercredi 25 juin 2025, 14:00 → 17:00 Europe/Paris

1R2 - 207 (Institut de Mathématiques de Toulouse)

https://univ-tlse3-fr.zoom.us/j/4533231833

 

Résumé : 

Les automates cellulaires peuvent être définis comme des systèmes dynamiques discrets qui actualisent des symboles d'un alphabet fini placés sur un réseau en fonction des symboles voisins de manière uniforme et synchrone. On s'intéresse dans cette thèse à des perturbations aléatoires de ces systèmes : chaque actualisation, de manière indépendante, a une probabilité d'être erronée. Lorsque cette perturbation devient négligeable et que la probabilité d'erreur tend vers 0, on appelle les points d'accumulation des mesures invariantes de l'automate cellulaire probabiliste associé les mesures 0-limites.

Dans un premier temps, on s'intéresse aux mesures 0-limites de certaines classes usuelles d'automates cellulaires. On montre cependant que le problème de savoir si une mesure de probabilité est une mesure 0-limite pour un automate cellulaire donné perturbé par un bruit standard est indécidable.

Dans un second temps, on précise quelles sont les contraintes topologiques et de calculabilité qui s'appliquent sur les ensembles de mesures 0-limites théoriquement possibles. Lorsque l'ensemble en question est uniformément approché, c'est alors nécessairement un compact connexe Π 2 -calculable. C'est en réalité une caractérisation, puisqu'on est capable de construire un automate cellulaire qui le réalise sous une perturbation standard.

Un automate cellulaire perturbé par un bruit à taux positifs est généralement ergodique: partant de n'importe quelle configuration, le système converge vers une unique mesure qui dépend uniquement du bruit. Il n'existe qu'un seul exemple d'automate cellulaire unidimensionnel dont la perturbation n'est pas ergodique, qui est très complexe et vrai uniquement pour une perturbation très faible. On l'utilise pour décrire dans un troisième temps un automate cellulaire dont la perturbation standard réalise deux changements de phase pour l'ergodicité. Plus précisément, l'automate cellulaire probabiliste associé est ergodique pour une perturbation assez faible et pour une perturbation assez forte, mais non-ergodique pour un taux d'erreur fixé entre les deux.

Enfin, on considère les questions précédentes appliquées aux fonctions continues d'un ensemble de Cantor sur lui-même. On montre ainsi qu'il est possible de construire une fonction continue dont la perturbation aléatoire est ergodique uniquement pour un taux d'erreurs appartenant à une intersection dénombrable d'ouverts de l'intervalle arbitraire.

 

 

Abstract :

Cellular automata can be defined as discrete dynamical systems that synchronously and uniformly update symbols from a finite alphabet placed on a network based on the neighboring symbols. In this thesis, we look at random perturbation of such systems: each update, independently, has a probability to make a mistake. When this perturbation becomes negligible and the probability of error tends to 0, the accumulation set of invariant measures of the probabilistic cellular automaton associated is called the set of 0-noise limit measures.

We first look at the 0-noise limit measures of some usual classes of cellular automata. We also show that the problem of deciding if a probability measure is a 0-noise limit measure of a given cellular automaton or not is actually undecidable.

We then compute several topological and computational constraints on the theoretical set of 0-noise limit measures. When this set of measures is uniformly approached, it is then necessarily a connected Π 2 -computable compact set. This is actually a characterization, as we are able to construct a cellular automaton realizing it when perturbed by a standard noise.

Following that, we also describe a cellular automaton whose perturbation by a standard noise realizes at least two phase transitions for its ergodicity. More precisely, the associated probabilistic cellular automaton is ergodic when the noise level is small enough or is large enough, but not ergodic for a given level in between.

A cellular automaton perturbed by a noise with positive rates is generally ergodic: starting from any configuration, the system converges to a unique measure that only depends on the noise. There exists only one example of a 1-dimensional cellular automaton whose perturbation is not ergodic, which is very complex and true only for a small perturbation. We use it in order to describe a cellular automaton whose perturbation by a standard noise realizes at least two phase transitions for its ergodicity. More precisely, the associated probabilistic cellular automaton is ergodic when the noise level is small enough or is large enough, but not ergodic for a given level in between.

Finally, we generalize the previous problems to the class of continuous functions on the set of configurations on itself. We show that one can construct such a continuous function whose probabilistic perturbation is only ergodic for an error level in a countable intersection of open sets on the unit interval.