Garden-of-Eden theorem

Edward F. Moore’s Garden-of-Eden theorem was the first rigorous statement of cellular automata theory. Though originally stated for cellular automata on the plane, it works in arbitrary dimension.

Theorem 1 (Moore, 1962)

Let $\mathrm{A}\mathrm{=}\mathrm{⟨}Q\mathrm{,}\mathrm{N}\mathrm{,}f\mathrm{⟩}$ be a cellular automaton on ${\mathrm{Z}}^d$ with finitely many states. If $\mathrm{A}$ has two mutually erasable patterns, then it has an orphan pattern.

In other words, surjective $d$-dimensional cellular automata are pre-injective.

The same year, John Myhill proved the converse implication.

Theorem 2 (Myhill, 1962)

Let $\mathrm{A}\mathrm{=}\mathrm{⟨}Q\mathrm{,}\mathrm{N}\mathrm{,}f\mathrm{⟩}$ be a cellular automaton on ${\mathrm{Z}}^d$ with finitely many states. If $\mathrm{A}$ has an orphan pattern, then it has two mutually erasable patterns.

In other words, pre-injective $d$-dimensional cellular automata are surjective.

Corollary 1

An injective $d$-dimensional cellular automaton is surjective.

Theorems 1 and 2 hold because of the following statement.

Lemma 1

Let $a\mathrm{>}\mathrm{0}$, $d\mathrm{\ge }\mathrm{1}$, $r\mathrm{\ge }\mathrm{1}$, $k\mathrm{\ge }\mathrm{1}$. For every sufficiently large $n$,

(1)

Observe that, if $a=|Q|$ and

$$𝒩=\{x\in {\mathbb{Z}}^d\mid |x_i|\le r\forall i\in \{1,\mathrm{\dots },d\}\},$$ (2)

then ${(a^{kn})}^d$ is the number of possible hypercubic patterns of side $kn$, while ${(a^{kn-2r})}^d$ is the maximum number of their images via $f$.

Proof. The inequality (1) is in fact satisfied precisely by those $n$ that satisfy

which is true for $n$ large enough since while ${lim}_{n\to \mathrm{\infty }}{(k-2r/n)}^d=k^d.$ $\mathrm{\square }$

For the rest of this entry, we will suppose that the neighborhood index $𝒩$ has the form (2).

Proof of Moore’s theorem. Suppose $𝒜$ has two mutually erasable patterns $p_1$, $p_2$: it is not restrictive to suppose that their common support is a $d$-hypercube of side $k$. Define an equivalence relation $\rho$ on patterns of side $n$ by stating that $p\rho q$ if and only if $f(p)=f(q)$: since $p_1$ and $p_2$ are mutually erasable, $\rho$ has at most ${|Q|}^{k^d}-1$ equivalence classes.

By the same criterion, we define a family ${\{{\rho }_n\}}_{n\ge 1}$ of equivalence relations between hypercubic patterns of side $kn$. Each such pattern can be subdivided into $n^d$ subpatterns of side $k$: and it is clear that, if two patterns are in relation ${\rho }_n$, then each of those subpatterns is in relation $\rho$.

But then, the relation ${\rho }_n$ cannot have more than ${({|Q|}^{k^d}-1)}^{n^d}$ equivalence classes: consequently, at most ${({|Q|}^{k^d}-1)}^{n^d}$ patterns of side $kn-2r$ can have a preimage. By Lemma 1 with $a=|Q|$, for $n$ large enough, some patterns of side $kn-2r$ must be orphan. $\mathrm{\square }$

Proof of Myhill’s theorem. Let $p$ be an orphan pattern for $𝒜$. Again, it is not restrictive to suppose that the support of $p$ is a hypercube of side $k$. For $n\ge 1$ let ${\nu }_n$ be the number of patterns of side $kn$ that are not orphan. Split each pattern of side $kn$ into $n^d$ patterns of side $k$, as we did before. Then ${\nu }_n$ cannot exceed the number of those that do not contain a copy of $p$, which in turn is at most ${({|Q|}^{k^d}-1)}^{n^d}$.

Take $n$ so large that (1) is satisfied: for a fixed state $q_0\in Q$, and for $q_1=f(q_0,\mathrm{\dots },q_0)$, there are more configurations that take value $q_0$ outside the hypercube ${\{0,\mathrm{\dots },kn-2r-1\}}^d$ than there are configurations that take value $q_1$ outside the hypercube ${\{-r,\mathrm{\dots },kn-1\}}^d$ and are not Gardens of Eden. As the configurations of the second type are the images of those the first type, there must be two with the same image: those configurations correspond to two mutually erasable patterns. $\mathrm{\square }$

Theorems 1 and  2 have been shown [2] to hold for cellular automata on amenable groups. Moore’s theorem, in fact, characterizes amenable groups (cf. [1]): whether Myhill’s theorem also does, is an open problem.

Title	Garden-of-Eden theorem
Canonical name	GardenofEdenTheorem
Date of creation	2013-03-22 19:22:07
Last modified on	2013-03-22 19:22:07
Owner	Ziosilvio (18733)
Last modified by	Ziosilvio (18733)
Numerical id	9
Author	Ziosilvio (18733)
Entry type	Theorem
Classification	msc 68Q80
Classification	msc 37B15