Posted by: Silvio Capobianco | 2013/06/27

In a Garden of Eden

The Garden-of-Eden theorem was the first rigorous result of cellular automata theory. It thus seems just fair to me that, after introducing the blog in my previous post, and having given talk about it during the Theory Lunch at the Institute of Cybernetics where I am working, I write a post about it on this blog.

The Garden-of-Eden theorem arose from the studies by Edward F. Moore about self-reproduction in distributed structures, a theme already discussed by John von Neumann in his groundbreaking work where the expression “cellular automaton” first appeared. In his 1962 paper[1], Moore was interested in the necessary conditions that a localized structure, considered as an island of states in a sea of quiescent states, could produce copies of itself after finitely many iterations. The original paper only considered the two-dimensional case, but the argument there immediately extends to arbitrary dimension.

Consider a $d$-dimensional configuration, obtained by associating to each point $x \in \mathbb{Z}^d$ a state $c(x) \in Q$ for some finite set $Q$. Suppose also that we have a cellular automaton $\mathcal{A}$, with global function $\mathcal{F}$, whose set of states is precisely $S$. We ask ourselves:

is there some $e : \mathbb{Z}^d \to S$ such that $F(e) = c$?

For example, consider Wolfram’s elemantary CA rule 102, where the next state of a cell is the exclusive OR (addition modulo 2) of its state with that of it rightmost neighbor: it is easy to check that each configuration has exactly two preimages.

If no such $e$ exists, we follow a suggestion by John Tukey and say that $c$ is a Garden-of-Eden: it can be started from, but not returned to. But how can we check if $c$ is a GoE?

A thing that the cellular automata formalism allows us to do, is to switch our point of view from global to local. Instead of doing our checks on whole configurations, we check patterns, that is, finite chunks of configurations: a pattern is defined by a support $E$, which is a finite subset of $\mathbb{Z}^d$, and a function $p : E \to Q$. In the same way as the local function $f$ defines the global function on configurations, it also defines, for every finite $E$, a function $f = f_E$ from the patterns with support $E + \mathcal{N} = \{ x + n \mid x \in E, n \in \mathcal{N} \}$ to those with support $E$. If a pattern $p : E \to Q$ has not predecessor according to $f_E$, we say that $p$ is an orphan. If for a configuration $c : \mathbb{Z}^d \to Q$ and a pattern $p : E \to Q$ there exists a point $k \in \mathbb{Z}^d$ such that $c(k+x) = p(x)$ for every $x \in E$, we say that $p$ occurs in $c$, and that $k$ is an occurrence of $p$ in $c$.

For example, consider Wolfram’s elemantary CA rule 232, the majority rule: the neighborhood of a cell is made of the cell itself with the ones immediately at its left and right, and the next state of the cell is the state currently taken by the majority of the three. It is then easy to check that the pattern $01101$ is an orphan.

Lemma 1. (Orphan pattern principle) A configuration is a Garden-of-Eden if and only if it has an occurrence of an orphan pattern.
In particular: a cellular automaton has no GoE configurations if and only if it has no orphan patterns.

Proof: One direction is immediate, so let us suppose that none of the patterns that occur in $c$ is orphan. We can thus construct a sequence of configurations $\mathcal{E} = \{e_n\}_{n \geq 0}$ such that $F(e_n)$ coincides with $c$ on the Moore neighborhood of radius $n$. Let $e$ be a limit point of $\mathcal{E}$, which exists because the space $\mathcal{C} = Q^{\mathbb{Z}^d}$ of configurations is compact: it is easy to see that $F(e) = c$. $\Box$

Definition 1. A cellular automaton with global function $F$ is pre-injective if it satisfies the following condition: if $c_1, c_2 : \mathbb{Z}^d \to Q$ are distinct asymptotic configurations, then $F(c_1) \neq F(c_2)$.

Informally, a pre-injective CA cannot correct finitely many errors in finite time. Pre-injectivity may also be restated by saying that, given an arbitrary configuration $c$, the CA is injective on the set $\mathrm{Asymp}(c)$ of configurations asymptotic to $c$. For if $c_1, c_2 : \mathcal{Z}^d \to Q$ are only different on $\mathcal{M}_n$ but $F(c_1) = F(c_2)$, then by setting $e_i(x) = c_i(x)$ for $x \in \mathcal{M}_{n+2r}$ where $r$ is the neighborhood radius, and $e_i(x) = q$ otherwise where $q \in Q$ is a fixed state, we easily see that $e_1 \neq e_2$ and $F(e_1) = F(e_2)$, thus the CA is not injective on $\mathrm{Asymp}(c_q)$ where $c_q(x) = q$ for every $x$.

Moore’s discovery was that pre-injectivity is a necessary condition for absence of Gardens-of-Eden.

Theorem 1. (Moore, 1962) If a $d$-dimensional cellular automaton is not pre-injective, then it has a Garden-of-Eden.

To prove this statement, we need numerical estimates of the number of patterns that are not orphan: such estimate is given by

Lemma 2. Let $q, n, s$ be positive integers. Then for every $k$ large enough,

$\left( q^{n^d} - 1 \right)^{k^d} < q^{(kn-s)^d}$

Proof: We can safely suppose $q > 1$. Then the above inequality is equivalent to

$\log_q \left( q^{n^d} - 1 \right) < \left( n - \frac{s}{k} \right)^d \;,$

which is true for every $k$ large enough. $\Box$

Proof of Theorem 1: Let $c_1, c_2 : \mathbb{Z}^d \to Q$ have $0 < |\Delta(c_1, c_2)| < \infty$ and $F(c_1) = F(c_2)$. Let $n$ be so large that $\Delta(c_1, c_2)$ is contained in a hypercube of side $n-2r$ where $r$ is the neighborhood radius: then there are at most $q^{n^d} - 1$ possible images of patterns with support a hypercube of side $n$, where $q = |Q|$ is the number of states. As a pattern over a hypercube of side $kn$ is a juxtaposition of $k^d$ (specifically, $k$ layers in each of the $d$ possible directions) patterns over hypercubes of side $n$, there are at most $\left( q^{n^d} - 1 \right)^{k^d}$ possible images of patterns with support a hypercube of side $kn$: but the number of such patterns is by construction $q^{kn-2r}$. By Lemma 2 with $s = 2r$, some such patterns must be orphan. $\Box$

Shortly after Moore presented his result, John Myhill[2] proved the converse implication.

Theorem 2. (Myhill, 1963) If a $d$-dimensional cellular automaton has a Garden-of-Eden, then it is not pre-injective.

Proof: By contradiction, assume that the CA is pre-injective but has an orphan pattern $p$, whose support $E$ is a hypercube of side $n$. Fix a state $q \in Q$ and let $c_q(x) = q$ for every $x$: by pre-injectivity, the CA is injective on $\mathrm{Asymp}(c_q)$, so there must be at least as many non-orphan patterns on a hypercube of side $kn$ as there are patterns on a hypercube of side $kn-2r$. But there are at most $\left( q^{n^d} - 1 \right)^{k^d}$ of the former and exactly $q^{{kn-2r}^d}$ of the latter: for $k$ large enough, this goes against Lemma 2. $\Box$

Corollary 1 (Garden-of-Eden theorem) A cellular automaton on $\mathbb{Z}^d$ is surjective if and only if it is pre-injective.

Corollary 2. An injective $d$-dimensional CA is surjective.

You might have noticed that the reason why the Garden-of-Eden theorem holds for cellular automata over $\mathbb{Z}^d$, is that the number of points within distance $n$ from the center grows polynomially with $n$. This is not always the case, however: one may want to consider CA on more complex grids, such as the free group on two generators, where such number grows exponentially with $n$.

And in fact, the majority rule on $\mathbb{F}_2$ is not pre-injective, as setting state $1$ either within or at distance $1$ from the origin, both update to state $1$ only in the origin: but it is surjective, because any state in the origin has a preimage, and if every state within distance $n$ has a preimage, then every state within distance $n+1$ can be given a preimage by first obtaining one for the state within distance $n$, then suitably setting the values of each of the three (of five) neighbors of the points at distance $n+1$ which are at distance $n+2$ from the origin.

References

1. Moore, E.F. (1962) Machine models of self-reproduction. Proc. Symposia in Applied Mathematics 14, 17–34.
2. Myhill, J. (1963) The converse of Moore’s Garden-of-Eden theorem. Proc. Amer. Math. Soc. 14, 685–686.
3. Ceccherini-Silberstein, T., Machí, A., and Scarabotti, F. (1999) Amenable groups and cellular automata. Ann. Inst. Fourier 49, 673–685.