Percolation and disorder-resistance in cellular automata
-
Gravner, Janko [2] ; Holroyd, Alexander E. [1]
-
[1] The Microsoft Research - University of Trento Centre for Computational and Systems Biology
The Microsoft Research - University of Trento Centre for Computational and Systems Biology
Trento, Italia
-
[2] University of California
-
- Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 43, Nº. 4, 2015, págs. 1731-1776
- Idioma: inglés
- DOI: 10.1214/14-AOP918
- Enlaces
-
Resumen
We rigorously prove a form of disorder-resistance for a class of one-dimensional cellular automaton rules, including some that arise as boundary dynamics of two-dimensional solidification rules. Specifically, when started from a random initial seed on an interval of length L, with probability tending to one as L→∞, the evolution is a replicator. That is, a region of space–time of density one is filled with a spatially and temporally periodic pattern, punctuated by a finite set of other finite patterns repeated at a fractal set of locations. On the other hand, the same rules exhibit provably more complex evolution from some seeds, while from other seeds their behavior is apparently chaotic. A principal tool is a new variant of percolation theory, in the context of additive cellular automata from random initial states.
