Stochastic cellular automata
What it's about
Cellular automata, introduced by von Neumann, are locally connected finite
automata whose dynamics, in spite of the limited power of its components
and local interaction, can be rich and arbitrarily complex. For example,
when viewed as an abstract computing machine, a cellular automaton (CA)
is capable of universal computation and represents a prototypical parallel
computer. When viewed as a physical system, a CA can be used to model
collective behavior of particle dynamics in physics, cellular interactions
in biology, and information processing in distributed computing systems.
Philosophically, CAs can embody a mindset where one's world view is that
of a giant CA, inclusive family of CAs, whose rules and secrets, through
scientific endeavor, one seeks to uncover.
Issues and challenges
My research focus in cellular automata is in the study of their dynamics
when treated as an abstract computing machine, i.e., mathematical discipline.
Physics, biology, and distributed computing systems in computer science
act as proving grounds where additional structure and constraints can
be injected to answer questions arising in the various domains and test
the theory's predictability. From a research perspective, CAs can quickly
become "uninteresting" due to their universality: many questions
involving their dynamics are undecidable. Those questions that have been
hereto answered for deterministic CAs can be highly nontrivial, but even
so, perhaps not impressively deep. Potentially interesting ideas, such
as Wolfram's 4-fold classification of CAs, have been studied, but little
rigorous underpinning exists to give them depth with respect to technical substance.
Overcoming this barrier looms as an important challenge.
The state of affairs for stochastic cellular automata is a little brighter:
it has enabled posing fundamental questions that have been solved, some
only partially, using novel ideas and mathematical arsenals in innovative
ways that have advanced the state-of-the-art. A canonical problem concerns
the reliability or (non)ergodicity of cellular automata, whose roots can
be traced to von Neumann's study of fault-tolerant computation in Boolean
circuits. In its simplest form, the CA reliability problem can be stated
as a "memory" problem: can a deterministic CA remember its past
when continually subject to noise?
Example: "Can you remember a single bit?" Consider a
2-state one-dimensional CA implementing majority voting a cell
inspects the state of its two nearest neighbors and itself, and chooses
as its next state the majority where at each transition point a
fault can occur with probability p. If a CA with an infinite
number of cells (for finite CA the problem is trivial although the convergence
rate is not) is started in a configuration where all cells are in state
1, will it continue to remember something about its initial configuration,
or will faults collude and erase all memory of its beginning with the
hands of time? Since the same CA can be started in a configuration where
all cells are in state 0, one can advance the interpretation: can an infinite
1-D CA remember a single bit when immersed in a noisy environment? Here
the meaning of remembering/storing is in its weakest form where we will
grant retrieval of a single bit if the CA can correctly guess whence it
came from with probability greater than 1/2.
Using an infinite 1-D CA to remember a single bit is a somewhat expensive
proposition. The question addressed therein, however, is of fundamental
value, more basic, in some respects, than applied questions such as whether
the universe is expanding/shrinking, or how cells organize themselves
into a multitude of organs and body parts during development. Understanding
developmental biology and cellular dynamics underlying cancer are clearly
practically relevant and in many ways more complicated, however, one suspects
that a necessary component for effectively combating disease and other
complex phenomena with a cellular basis is a better understanding of the
fundamentals which our effort is aimed at.
Toom's seminal work in the early '70s showed the existence of nonergodic
cellular automata in dimension 2 and higher. Gray (1982) proved that continuous
time 1-D CA implementing majority voting are forgetful. Gacs (1986) constructed
discrete time 1-D CA that are nonforgetful, refuting the positive rates
conjecture which had been accepted by many in the community. My contribution
(1996) showed that certain 1-D cellular automata proposed in the '70s
and '80s as candidates of nonergodic CA are forgetful if there is a bias
in the error model. This work also showed that convergence, as measured
by relaxation time, is significantly faster, i.e., exp[O(log2 1/p)],
than the exponential rate conjectured by some in the community. Relaxation
time has implications to finitary systems and their resilience to noise.
Eroder property: "Contain the enemy!" Gacs, Kurdyumov
and Levin (1978) proposed a 2-state CA, also called the GKL, soldiers,
or unsymmetric voter rule, which has the property that any finite island
of non-1's within a sea of 1's will be erased in finite time. This deterministic
error correcting property, called eroder property, is illustrated in Fig.
1 (a) where a finite island of 0's (black cells) is eventually erased
when placed amidst a sea of 1's (white cells). The "grey" colored
space-time triangle is actually a pattern of alternating 0's and 1's which
comes across visually as grey. The GKL rule is defined as follows: if
the state of a cell is 0, then it takes the majority vote of the first
neighbor to its right, the third neighbor to its right, and itself. If
the state of the cell is 1, it does so in the opposite direction. Toom
introduced a 4-state CA possessing the eroder property, called two-line
voting, in an attempt to have a technically more amenable symmetric rule
(Toom's proof of nonergodicity in dimension 2 or higher heavily relied
on symmetric rules with certain basins of attraction). The dynamics of
deterministic two-line voting is shown in Fig. 1 (b). An island of black
is erased within a sea of white; the red and green space-time triangles
denote the other two states of the CA.
Impact of noise: "Tale of dancing snakes" When the deterministic
CA dynamics is subject to noise, the "signalling" affecting
error correction is disrupted resulting in a complex boundary or interface
at the junction where a largely "blackish" region meets a largely
"whitish" region. Fig. 2 (a) and (b) show the stochastic dynamics
of the GKL and two-line voting rules under the same initial condition
as Fig. 1 when transitions are subject to noise. Understanding the evolution
of the stochastic CAs is tantamount to understanding the behavior of the
fluctuating boundaries, in relation to the time scale at which black (or
white) islands of size m get spontaneously born. The error model
is symmetric if the probability of erring toward any one of the states
during transition is uniform; it is asymmetric, i.e., possesses a bias,
if the transition probability is non-uniform.
Intuitively, if the error model is symmetric, one might expect that boundaries
behave akin to a symmetric random walk (assuming the width of the interface
remains well-behaved), with adjacent boundaries annihilating each other
when they meet: i.e., the island wedged between two boundaries is erased.
If the error model is asymmetric e.g., there is a bias toward black
when errors occur in a transition then one may conjecture that
the boundary behaves like a random walk with drift, which may result in
blackish islands tending to expand and whitish islands tending to contract.
Hence, even if a CA is started from an initial configuration of all white,
black islands, upon spontaneously arising, will tend to survive and merge,
leading to an equilibrium in the limit where the probability measure in
the space of all configurations is concentrated on blackish configurations.
Proof: "Talk the talk, walk the walk" The random walk
intuition and the behavior of boundaries resembling contact and branching
processes sounds plausible, but how does one go about proving ergodicity?
The boundary looks unwieldy and saying anything rigorous about its evolution
appears daunting. It turns out that a multi-resolution analysis framework
related to renormalization in statistical mechanics pioneered
by Gacs in the context of proving nonergodicity of 1-D cellular automata
can be harnessed to prove ergodicity of GKL and two-line voting in the
opposite context of showing forgetfulness of 1-D CA that possess the eroder
property. The proof structure has two key components: one combinatorial
and the other probabilistic (in a very broad sense, it can be viewed as
a sample path method). On the combinatorial side, one wishes to characterize
space-time rectangles for both the CA evolution as well as the error pattern,
with which one can cover, or patch together, the entire space-time evolution
such that "neighboring" space-time rectangles obey the laws
of motion dictated by the CA rule. Keeping track of the future, given
the complicated nature of the boundary, becomes progressively harder with
time. The trick is to compensate for this loss of resolution by adopting
a coarser, yet rigorous, viewpoint of the dynamics with increasing time
whose dynamics, at the coarser scale, remains exact.
The aforementioned space-time rectangles, therefore, increase in size,
and to enable causally consistent assembly of these rectangles to cover
all of space-time, their internal shape/pattern, as a function of size,
is defined recursively. The key notion for defining such causally patchable
rectangles is that of (recursive) sparsity. For example, in the case of
space-time error patterns under a given error model, we would call a larger
space-time rectangle k-sparse if the rectangle, modulo a possible
"glitch" that can be covered/excluded by a smaller rectangle,
is (k-1)-sparse. For a biased error model, the base level (k
= 0) definition would assert that "good" errors (e.g., those
helping black) are in simple dominance over "bad" errors (e.g.,
those helping white). At level k, this dominance holds recursively
so, where coarsity admits allowances for self-similar/fractal violations.
In the case of space-time evolution patterns, a similar recursive sparsity
notion applies where k-blackness captures dominance of black
cells over white cells in a space-time rectangle with allowances for fractally
distributed holes (think of Swiss cheese). This undertaking, albeit in
a more combinatorial sense, is akin to setting up multi-scale differential
equations and integrating across both scale and time to find a solution
of the behavior of the system in the long run at ever coarser scale.
The probabilistic component of the proof is two-fold. First, one must
show that k-sparse error patterns are typical: for independent
errors the probability of not being k-sparse is superexponentially
small. This property, called the sparsity lemma, is then combined with
the deterministic dynamics of the combinatorial part to conclude that
the probability of a space-time rectangle in the stochastic CA evolution
is not k-black is small. The second part of the probabilistic
component concerns the stochastic framework for proving ergodity. We use
coupling where, considering the relative magnitude of the probability
of k-blackness and the birth probability of black islands, we
show that the region of agreement of the coupled system grows. An innovation
of the stochastic framework is that coupling can be made to work for the
asymmetric GKL rule. For two-line voting, which is symmetric, an FKG-type
inequality that couples the all-0 configuration with the all-1 configuration
"sandwiching" all other trajectories in-between facilitates
proof of ergodicity. In the case of the GKL rule, we define a coupling
that simultaneously glues all trajectories over a common probability space
and show that agreement spreads for any pair of trajectories.
Is the GKL rule ergodic under symmetric errors?
The conjecture is, "yes." The unique invariant measure may be equally
blackish-whitish flavoured space-time patterns to which both the all-black
and all-white configurations (and all other configurations) converge.
Proving that this is so presents interesting challenges.
Considering other fault models, establishing
a rigorous correspondence between relaxation time of infinite systems
and rate of information loss in finite systems, constructing simpler
nonergodic 1-D CAs (if they exist) are avenues that may be further
This is joint work with Peter Gacs, my Ph.D. thesis advisor at BU.
The research was supported in part by NSF grant CCR-9002614.
- Peter Gacs. Reliable computation with cellular automata. Journal
of Computer and System Sciences, 32(1):15-78, 1986.
- P. Gacs, G. Kurdyumov, and L. Levin. One-dimensional homogeneous
media dissolving finite islands. Problems of Information Transmission,
- Lawrence Gray. The positive rates problem for attractive nearest
neighbor spin systems on Z. Z. Wahrscheinlichkeitstheorie
verw. Gebiete, 61:389-404, 1982.
- Kihong Park. Ergodicity and mixing rate of one-dimensional cellular
automata. Ph.D. Thesis, Boston University, 1996.
- Andrei Toom. Nonergodic multidimensional systems of automata. Problems
of Information Transmission, 10:239-246, 1974.
- John von Neumann. Theory of Self-Reproducing Automata (edited
and completed by A. Burks). University of Illinois Press, 1966.