Characterization of the set of zero-noise limits measures of perturbed cellular automata

Marsan Hugo, Sablik Mathieu · 2024

Read Characterization of the set of zero-noise limits measures of perturbed cellular automata by Marsan Hugo, Sablik Mathieu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04672.txt.

Introduction

Hugo Marsan and Mathieu Sablik study noise in cellular automata in a 2024 arXiv paper. They add small random errors to a cellular automaton and watch the steady patterns as the noise shrinks toward zero. The question is which invariant distributions can survive that limit.

They show the limit set is always compact and connected, and they pin down its computability class. In reverse, any set with those traits can be built from some automaton under uniform noise. Changing the noise bias changes the picture wildly. One automaton they build can realize any connected compact set under a slight bias shift.

Catalog record

CREATORMarsan Hugo, Sablik Mathieu
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE119 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-04672

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Characterization of the set of zero-noise limits measures of perturbed cellular automata Marsan Hugo, Sablik Mathieu Abstract . We add small random perturbations to a cellular automaton and consider the one-parameter family ( F ϵ ) ϵ > 0 (F_{\epsilon})_{\epsilon>0} parameterized by ϵ \epsilon where ϵ > 0 \epsilon>0 is the level of noise. The objective of the article is to study the set of limiting invariant distributions as ϵ \epsilon tends to zero denoted ℳ 0 l \mathcal{M}_{0}^{l} . Some topological obstructions appear, ℳ 0 l \mathcal{M}_{0}^{l} is compact and connected, as well as combinatorial obstructions as the set of cellular automata is countable: ℳ 0 l \mathcal{M}_{0}^{l} is Π 3 \Pi_{3} -computable in general and Π 2 \Pi_{2} -computable if it is uniformly approached. Reciprocally, for any set of probability measures 𝒦 \mathcal{K} which is compact, connected and Π 2 \Pi_{2} -computable, we construct a cellular automaton whose perturbations by an uniform noise admit 𝒦 \mathcal{K} as the zero-noise limits measure and this set is uniformly approached. To finish, we study how the set of limiting invariant measures can depend on a bias in the noise. We construct a cellular automaton which realizes any connected compact set (without computable constraints) if the bias is changed for an arbitrary small value. In some sense this cellular automaton is very unstable with respect to the noise. 1. Introduction A cellular automaton is a complex system defined by a local rule which acts synchronously and uniformly on the configuration space \mathcal{A}^{\mathbb{Z}} , where \mathcal{A} is a finite alphabet. It can be also defined as a continuous function on \mathcal{A}^{\mathbb{Z}} which commutes with the shift. These simple models have a wide variety of different dynamical behaviours. Cellular automata are used to model phenomena defined by local rules or to implement massively parallel computations. The set of invariant probability measures of the system, denoted by \mathcal{M}_{0} , gives information on the statistical properties of the system. Since physical models have some uncertainty, it is natural to perturb a dynamical system at each iteration. From the computer science point of view, these perturbations allow to explore how the model is robust at some noise. A natural way to define a perturbation is to consider that after each iteration of a given cellular automaton, we randomly modify each cell independently with a probability \epsilon where the new letter is chosen uniformly: we call this the uniform perturbation. The set of stationary probability measures of this randomly perturbed dynamics is denoted by \mathcal{M}_{\epsilon} . For many classes of cellular automata, \mathcal{M}_{\epsilon} is a singleton [ 13 ] . It was historically more difficult to find cellular automata such that \mathcal{M}_{\epsilon} is not a singleton [ 20 ] and the question was very challenging for one dimensional cellular automata [ 7 ] . In this article, we consider the set of zero-noise limits of invariant measures of the perturbed dynamical systems as \epsilon tends to zero, denoted by \mathcal{M}_{0}^{l} . Its corresponds to the set of accumulation points of the sets \mathcal{M}_{\epsilon} when \epsilon goes to 0 . \mathcal{M}_{0}^{l} is actually a subset of \mathcal{M}_{0} and can be seen as a way to select physically relevant invariant measures of the system. Informally it is an invariant measure which is supposed to be observable even if there is some noise. Usually, one can look for conditions on the dynamical system to force \mathcal{M}_{0}^{l} to be a singleton: the dynamical system is then said to be strongly stochastically stable. In the context of smooth dynamical systems. L.S. Young proves the stochastic stability of \mathcal{C}^{2} hyperbolic diffeomorphism which comes from the persistence of hyperbolic attractors [ 24 ] . This problematic was explored for different class of dynamical systems [ 1 , 2 ] sometimes using specific methods as spectral properties of transfer operators [ 22 ] . See [ 25 ] for an overview. In the context of cellular automata the authors have proven the strong stochastic stability for some classes of cellular automata and the undecidability of this property [ 14 ] . The objective of this article is to characterize which set of invariant measures can be obtained as \mathcal{M}_{0}^{l} for a cellular automaton perturbed by a uniform noise. In particular we exhibit a wide variety of sets which can be reached as \mathcal{M}_{0}^{l} . The same question is also relevant for other classes of dynamical systems. Note that for large classes of cellular automata \mathcal{M}_{\epsilon} is a singleton [ 13 ] : in this case if \mathcal{M}_{0}^{l} is not a singleton, the stationary probability measure of the randomly perturbed dynamics associated can oscillate between different measures when \epsilon goes to 0 . We can generalize this phenomenon: \mathcal{M}_{0}^{l} is said to be uniformly approached if for any family (\pi_{\epsilon})_{\epsilon>0} of measures such that \pi_{\epsilon}\in\mathcal{M}_{\epsilon} the adherence values of the family is the whole \mathcal{M}_{0}^{l} . In other words, the description of \mathcal{M}_{0}^{l} does not depend of the family of invariant measures chosen. If \mathcal{M}_{0}^{l} contains at least two elements and is uniformly approached, the system is chaotic in the sense that there is no stable measure. A stable measure \mu is an invariant measure such that there exists a family of measures (\pi_{\epsilon})_{\epsilon>0} such that \pi_{\epsilon}\in\mathcal{M}_{\epsilon} and (\pi_{\epsilon})_{\epsilon>0} converges toward \mu when \epsilon goes to 0 . In this article we construct sets of zero-noise limits measures which are uniformly approached and so the cellular automata constructed are chaotic when \mathcal{M}_{0}^{l} is not a singleton. This notion of chaocity can be compared to the chaocity studied in [ 5 ] in the context of Gibbs measures defined by local range: when the temperature goes to 0 the Gibbs measures oscillate between two states of the ground states (measures obtained as adherence values of Gibbs measures when the temperature goes to 0 ). In [ 9 ] the notion of ground states uniformly approached is introduced in view to characterize them geometrically. To characterize sets realized as some \mathcal{M}_{0}^{l} , natural topological obstructions appear and are exhibited in Section 3 . The set \mathcal{M}_{0}^{l} is closed (so compact) as adherence values in the set of probability measures and is also connected. As the class of cellular automata is countable, there is also combinatorial obstructions which must appear to describe the possible zero-noise limits of invariant measures sets. Recently, a lot of dynamical invariants of cellular automata or subshift of finite type were characterized using computability tools (possible entropies [ 12 ] , possible growth-type invariants [ 16 ] , possible sub-actions [ 11 , 3 ] , possible limit measures [ 10 ] …). Thus it is natural to search such obstructions in this context. In Section 4 we introduce some notion of computability. A way to describe the algorithmic complexity of a compact set is to consider the next decision problem: given a ball in input, we ask if it intersects the compact set. As we consider asymptotic behavior, this decision problem is undecidable so we need to use the arithmetical hierarchy [ 19 ] to precise the level of uncomputability of this decision problem. In this setting, \mathcal{M}_{0}^{l} is \Pi_{3} -computable and if \mathcal{M}_{0}^{l} is uniformly approached it is \Pi_{2} -computable. A difficult question is

Read the complete text