Ergodicity of some classes of cellular automata subject to noise
arXiv:1712.05500 · doi:10.1214/19-EJP297
Abstract
Cellular automata (CA) are dynamical systems on symbolic configurations on the lattice. They are also used as models of massively parallel computers. As dynamical systems, one would like to understand the effect of small random perturbations on the dynamics of CA. As models of computation, they can be used to study the reliability of computation against noise. We consider various families of CA (nilpotent, permutive, gliders, CA with a spreading symbol, surjective, algebraic) and prove that they are highly unstable against noise, meaning that they forget their initial conditions under slightest positive noise. This is manifested as the ergodicity of the resulting probabilistic CA. The proofs involve a collection of different techniques (couplings, entropy, Fourier analysis), depending on the dynamical properties of the underlying deterministic CA and the type of noise.
38 pages, 10 figures; Improved presentation in few places, added to bibliography, corrected the statement of Lemma 4.5
References in corpus (10)
- Reliable Cellular Automata with Self-Organization
- Invariant Measures and Convergence for Cellular Automaton 184 and Related Processes
- Stationary measures and phase transition for a class of probabilistic cellular automata
- Cesaro mean distribution of group automata starting from measures with summable decay
- A non-ergodic probabilistic cellular automaton with a unique invariant measure
- Statistical Mechanics of Surjective Cellular Automata
- Ergodicity of PCA: Equivalence between Spatial and Temporal Mixing Conditions
- On Nilpotency and Asymptotic Nilpotency of Cellular Automata
- Invariant Measures and Decay of Correlations for a Class of Ergodic Probabilistic Cellular Automata
- Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches