Garden-of-Eden theorem

Edward F. Moore’s Garden-of-Eden theoremwas 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 satisfiedprecisely by those $n$ that satisfy

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

For the rest of this entry, we will supposethat 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 supportis 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 subdividedinto $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 supposethat 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 thosethat 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 typeare 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  2have 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.