thumb|upright=1.35|A Garden of Eden in [[Conway's Game of Life, discovered by R. Banks in 1971.

The successor of a configuration is another configuration, formed by applying the update rule simultaneously to every cell.

The transition function of the automaton is the function that maps each configuration to its successor.

A pattern, for a given cellular automaton, consists of a finite set of cells together with a state for each of those cells. A configuration contains a pattern when the states of the cells in the pattern are the same as the states of the same cells in the configuration (without translating the cells before matching them). The definition of predecessors of configurations can be extended to predecessors of patterns:

a predecessor of a pattern is just a configuration whose successor contains the pattern. An orphan, then, is a pattern with no predecessor. Nevertheless, in many cases it is possible to use the Garden of Eden theorem (below) to infer that a solution exists and then use a search algorithm to find one.

It would be possible for a computer program to search for orphan patterns by systematically examining all finite patterns, in order by increasing size, and by testing all possible predecessors for each pattern to determine whether it is in fact an orphan. However, the number of patterns that would need to be generated to find a Garden of Eden in this way is exponential in the area of the pattern. This enormous number of patterns would make this type of brute-force search prohibitively expensive, even for relatively small sizes of patterns.

pioneered a more efficient computational approach for finding orphan patterns. His method is based on the theory of formal languages, and takes an amount of time that is exponential in the width of the pattern rather than its area. The key idea is that, for any fixed width, it is possible to construct a nondeterministic finite automaton that recognizes patterns of a given width that have a predecessor. The input symbols to this machine describe each row of the pattern, and the states of the machine describe the nearby rows of possible predecessors for the part of the pattern that has been input so far. One can construct from this machine another finite state machine that recognizes the complementary set, the patterns that do not have predecessors, by converting the nondeterministic finite state machine to a deterministic finite automaton by using the powerset construction, and then complementing its set of accepting states. Once a machine recognizing the complementary set has been constructed, one may test whether the language it recognizes is empty, by searching for a path from the start state to an accepting state. This path, if it exists, gives a row-by-row description of an orphan pattern.

Martin Gardner credits Alvy Ray Smith with the observation that the Garden of Eden theorem applies to Conway's Game of Life, and proves the existence of Gardens of Eden for this rule.

The first explicit Garden of Eden in Life, with its live cells fitting in a rectangle, was identified as a candidate to be a Garden of Eden by Roger Banks in 1971, and then verified by an exhaustive backtracking search for predecessors.

Subsequently, Hardouin-Duparc used his formal language approach to find the narrowest possible Gardens of Eden in Conway's Game of Life, with the bounding box for their live cells being only six cells wide.

The smallest known orphan pattern in Conway's Game of Life (by area of its bounding box) was found by Steven Eker in April 2016. It has 57 living cells and fits in an 8×12 rectangle.

Existence of orphans

By definition, every orphan belongs to a Garden of Eden: extending an orphan to a configuration of the whole automaton, by choosing a state for each remaining cell arbitrarily, will always produce a Garden of Eden. But the reverse is also true: every Garden of Eden contains at least one orphan.

To prove this, Kari uses a topological argument, based on the Curtis–Hedlund–Lyndon theorem according to which the transition functions of cellular automata are exactly the translation-invariant continuous functions on the space of configurations. Here, continuity is defined by assigning a discrete topology to the finite set of states of the automaton, and then using a product topology with one term in the product for each cell in the automaton to construct a topological space whose points are the automaton's configurations. By Tychonoff's theorem it is a compact space.

In non-Euclidean geometries

In cellular automata defined over tessellations of the hyperbolic plane, or of higher-dimensional hyperbolic spaces, the counting argument in the proof of the Garden of Eden theorem does not work, because it depends implicitly on the property of Euclidean spaces that the boundary of a region grows less quickly than its volume as a function of the radius. There exist hyperbolic cellular automata that have twins but that do not have a Garden of Eden, and other hyperbolic cellular automata that have a Garden of Eden but do not have twins; these automata can be defined, for instance, in a rotation-invariant way on the uniform hyperbolic tilings in which three heptagons meet at each vertex, or in which four pentagons meet at each vertex.

However, the Garden of Eden theorem can be generalized beyond Euclidean spaces, to cellular automata defined on the elements of an amenable group. A weaker form of the Garden of Eden theorem asserts that every injective cellular automaton is surjective. It can be proven for sofic groups using the Ax–Grothendieck theorem, an analogous relation between injectivity and bijectivity in algebraic geometry. More generally, the groups for which this weaker form holds are called surjunctive groups. There are no known examples of groups that are not surjunctive.

In fiction

In Greg Egan's novel Permutation City, the protagonist uses a Garden of Eden configuration to create a situation in which a copy of himself can prove that he is living within a simulation. Previously all his simulated copies had found themselves in some variant of the "real world"; although they had memories of being simulated copies living in a simulation, there was always a simpler explanation for how those memories came to be. The Garden of Eden configuration, however, cannot occur except in an intelligently designed simulation. The religious parallels are intentional.

Notes

References

  • ; see in particular pp. 230 and 248
  • ; reprinted in .
  • ; reprinted in .
  • Garden of Eden on LifeWiki
  • Garden of Eden (Eric Weisstein's Treasure Trove of The Game of Life)