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, 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 -dimensional configuration, obtained by associating to each point a state for some finite set . Suppose also that we have a cellular automaton , with global function , whose set of states is precisely . We ask ourselves:
is there some such that ?
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 exists, we follow a suggestion by John Tukey and say that is a Garden-of-Eden: it can be started from, but not returned to. But how can we check if 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 , which is a finite subset of , and a function . In the same way as the local function defines the global function on configurations, it also defines, for every finite , a function from the patterns with support to those with support . If a pattern has not predecessor according to , we say that is an orphan. If for a configuration and a pattern there exists a point such that for every , we say that occurs in , and that is an occurrence of in .
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 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 is orphan. We can thus construct a sequence of configurations such that coincides with on the Moore neighborhood of radius . Let be a limit point of , which exists because the space of configurations is compact: it is easy to see that .
Definition 1. A cellular automaton with global function is pre-injective if it satisfies the following condition: if are distinct asymptotic configurations, then .
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 , the CA is injective on the set of configurations asymptotic to . For if are only different on but , then by setting for where is the neighborhood radius, and otherwise where is a fixed state, we easily see that and , thus the CA is not injective on where for every .
Moore’s discovery was that pre-injectivity is a necessary condition for absence of Gardens-of-Eden.
Theorem 1. (Moore, 1962) If a -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 be positive integers. Then for every large enough,
Proof: We can safely suppose . Then the above inequality is equivalent to
which is true for every large enough.
Proof of Theorem 1: Let have and . Let be so large that is contained in a hypercube of side where is the neighborhood radius: then there are at most possible images of patterns with support a hypercube of side , where is the number of states. As a pattern over a hypercube of side is a juxtaposition of (specifically, layers in each of the possible directions) patterns over hypercubes of side , there are at most possible images of patterns with support a hypercube of side : but such images are hypercubic patterns of side , and the total number of the latter is by construction . By Lemma 2 with , some such patterns must be orphan.
Shortly after Moore presented his result, John Myhill proved the converse implication.
Theorem 2. (Myhill, 1963) If a -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 , whose support is a hypercube of side . Fix a state and let for every : by pre-injectivity, the CA is injective on , so there must be at least as many non-orphan patterns on a hypercube of side as there are patterns on a hypercube of side . But there are at most of the former and exactly of the latter: for large enough, this goes against Lemma 2.
Corollary 1 (Garden-of-Eden theorem) A cellular automaton on is surjective if and only if it is pre-injective.
Corollary 2. An injective -dimensional CA is surjective.
You might have noticed that the reason why the Garden-of-Eden theorem holds for cellular automata over , is that the number of points within distance from the center grows polynomially with . 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 .
And in fact, the majority rule on is not pre-injective, as setting state either within or at distance from the origin, both update to state only in the origin: but it is surjective, because any state in the origin has a preimage, and if every state within distance has a preimage, then every state within distance can be given a preimage by first obtaining one for the state within distance , then suitably setting the values of each of the three (of five) neighbors of the points at distance which are at distance from the origin.
- Moore, E.F. (1962) Machine models of self-reproduction. Proc. Symposia in Applied Mathematics 14, 17–34.
- Myhill, J. (1963) The converse of Moore’s Garden-of-Eden theorem. Proc. Amer. Math. Soc. 14, 685–686.
- Ceccherini-Silberstein, T., Machí, A., and Scarabotti, F. (1999) Amenable groups and cellular automata. Ann. Inst. Fourier 49, 673–685.