PERCOLATION AND DISORDER-RESISTANCE IN CELLULAR AUTOMATA

• 成果类型: Article
• 署名作者: Gravner, Janko; Holroyd, Alexander E.
• 署名单位: University of California System; University of California Davis; Microsoft
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/14-AOP918
• 发表日期: 2015
• 页码: 1731-1776
• 关键词: bootstrap percolation; dependent percolation; replication; dimensions; snowflakes; threshold; Seeds

摘要

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 -> infinity, 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.