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 A=Q,N,f be a cellular automatonMathworldPlanetmath on Zd with finitely many states. If A has two mutually erasable patterns, then it has an orphan pattern.

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

The same year, John Myhill proved the converse implication.

Theorem 2 (Myhill, 1962)

Let A=Q,N,f be a cellular automaton on Zd with finitely many states. If 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 injectivePlanetmathPlanetmath d-dimensional cellular automaton is surjective.

Theorems 1 and 2 hold because of the following statement.

Lemma 1

Let a>0, d1, r1, k1. For every sufficiently large n,

(akd-1)nd<a(kn-2r)d (1)

Observe that, if a=|Q| and

𝒩={xd|xi|ri{1,,d}}, (2)

then (akn)d is the number of possible hypercubic patterns of side kn, while (akn-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 loga(akd-1)<kd while limn(k-2r/n)d=kd.

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

Proof of Moore’s theorem. Suppose 𝒜 has two mutually erasable patterns p1, p2: it is not restrictive to suppose that their common supportMathworldPlanetmath is a d-hypercube of side k. Define an equivalence relationMathworldPlanetmath ρ on patterns of side n by stating that pρq if and only if f(p)=f(q): since p1 and p2 are mutually erasable, ρ has at most |Q|kd-1 equivalence classesMathworldPlanetmath.

By the same criterion, we define a family {ρn}n1 of equivalence relations between hypercubic patterns of side kn. Each such pattern can be subdivided into nd subpatterns of side k: and it is clear that, if two patterns are in relationMathworldPlanetmath ρn, then each of those subpatterns is in relation ρ.

But then, the relation ρn cannot have more than (|Q|kd-1)nd equivalence classes: consequently, at most (|Q|kd-1)nd patterns of side kn-2r can have a preimageMathworldPlanetmath. By Lemma 1 with a=|Q|, for n large enough, some patterns of side kn-2r must be orphan.

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 n1 let νn be the number of patterns of side kn that are not orphan. Split each pattern of side kn into nd patterns of side k, as we did before. Then νn cannot exceed the number of those that do not contain a copy of p, which in turn is at most (|Q|kd-1)nd.

Take n so large that (1) is satisfied: for a fixed state q0Q, and for q1=f(q0,,q0), there are more configurationsMathworldPlanetmathPlanetmath that take value q0 outside the hypercube {0,,kn-2r-1}d than there are configurations that take value q1 outside the hypercube {-r,,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.

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.


  • 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 converseMathworldPlanetmath 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