Condensed Matter Journal Club: "Random Local Dynamics as Self-Correcting Memory
"

Abstract: Cellular automata are systems of simple units arranged on a grid, where each unit changes its state by looking only at its nearby neighbors. Despite this simplicity, they can describe remarkably rich behavior. They have been used to design fault-tolerant classical and quantum memories that detect and repair errors using only local information, to model population dynamics, and to understand collective processes inside living cells.

Most cellular automata assume that every unit updates at the same instant. Real physical and biological systems, however, do not share a perfect global clock: different parts change at different and often random times. Such asynchronous cellular automata are therefore more realistic, but also much harder to understand analytically.

Several asynchronous rules are known numerically to preserve information even while errors are continually introduced. Yet there has been no general analytical method for proving this behavior, especially when the rule is intrinsically probabilistic. In this talk, I will review the history of this problem and present a rigorous stability criterion for a broad class of such systems. The central idea is simple: if errors are reliably removed within sufficiently large regions of space and time, then weak, continually occurring noise cannot accumulate enough to corrupt macroscopically stored information. Our framework explains why several previously mysterious probabilistic rules remain stable and provides a practical route for discovering new noise-resistant forms of local dynamics.