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{\u27e8}Q\mathrm{,}\mathrm{N}\mathrm{,}f\mathrm{\u27e9}$ 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{\u27e8}Q\mathrm{,}\mathrm{N}\mathrm{,}f\mathrm{\u27e9}$ 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.
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
$$\mathcal{N}=\{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 $\mathcal{N}$ has the form (2).
Proof of Moore’s theorem. Suppose $\mathcal{A}$ 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 $\mathcal{A}$. 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.
References
- 1 Bartholdi, L. (2010) Gardens of Eden and amenability on cellular automata. J. Eur. Math. Soc. 12(1), 141–148. Preprint: arXiv:0709.4280v1
- 2 Ceccherini-Silberstein, T., Machì, A. and Scarabotti, F. (1999) Amenable groups and cellular automata. Annales de l’Institut Fourier, Grenoble 49(2), 673–685.
- 3 Moore, E.F. (1962) Machine models of self-reproduction. Proc. Symp. Appl. Math. 14, 17–33.
- 4 Myhill, J. (1962) The converse^{} of Moore’s Garden-of-Eden theorem. Proc. Amer. Mat. Soc. 14, 685–686.
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 |