Percolation and disorder-resistance in cellular automata (Q2354150): Difference between revisions

The authors consider a large class of 3-state cellular automata in one space-dimension satisfying certain criteria. They rigorously prove what they call \textit{disorder resistance}, a phenomenon which contradicts the following intuition from statistical physics. One expects that if certain initial conditions in a dynamical system lead to chaotic behaviour, most initial conditions would also lead to chaotic behaviour, with some exceptional ones leading to regular behaviour. The authors prove that on the one hand, random bounded initial conditions lead almost surely to some sort of periodicity, a precisely defined structure which they call a \textit{replicator}. On the other hand, for unbounded initial conditions, they show that there is a nonzero probability of having a considerably more complex structure (although they do not prove chaotic behaviour). This complex structure is related to \textit{supercritical percolation} and they prove the latter result using techniques from percolation theory. The results involve a detailed study of a specific 2-state cellular automaton known as the \textit{1 or 3 rule}.