Garden of Eden (cellular automaton)

An orphan pattern in Conway's Game of Life, discovered by R. Banks in 1971.^[1]

A 12x11 orphan pattern in Conway's Game of Life, found by Achim Flammenkamp. Black squares are required ON cells; blue x's are required OFF cells.

In a cellular automaton, a Garden of Eden configuration is a configuration that cannot appear on the lattice after one time step, no matter what the initial configuration. In other words, these are the configurations with no predecessors.

They resemble the concept of the Garden of Eden in Abrahamic religions, which was created out of nowhere, hence the name. According to Moore (1962), this name was coined by John Tukey in the 1950s.

A Garden of Eden is a configuration of the whole lattice (usually a one- or two-dimensional infinite square lattice). Each Garden of Eden configuration contains at least one finite pattern (an assignment of states to a finite subset of the cells) that has no predecessor regardless of how the surrounding cells are filled. Such a pattern is called an orphan. Alternatively, an orphan is a finite pattern such that each configuration containing that pattern is a Garden of Eden.

Searching for the Garden of Eden

It would be possible for a computer program to search for Garden of Eden patterns by systematically examining all possible patterns, in order by increasing size, and by testing all possible predecessors for each pattern to determine whether it is in fact a Garden of Eden. 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 approach prohibitively expensive, even for relatively small sizes of patterns.

Jean Hardouin-Duparc (1972/73, 1974) pioneered a more efficient computational approach for finding orphan patterns, based on the theory of formal languages, that is exponential in the width of the pattern rather than its area. The key idea is that, for any fixed width, it is relatively straightforward to construct a nondeterministic finite state machine 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 state machine 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.

The first known Garden of Eden pattern in Conway's Game of Life, fitting in a 9 × 33 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.^[1] Subsequently, Hardouin-Duparc used his formal language approach to find the narrowest possible Gardens of Eden in Conway's Game of Life, only six cells wide. The smallest known orphan pattern in Conway's Game of Life was found by Nicolay Beluchenko on September 6, 2009.^[2] It has 69 living cells and fits in an 11x11 rectangle.

The Garden of Eden theorem

In a cellular automaton, two finite patterns are twins if one can be substituted for the other wherever it appears, without changing future states. A cellular automaton is injective if every pair of distinct configurations of the automaton remain different after a step of the automaton, and locally injective if it has no twins. It is surjective if and only if every configuration has a predecessor; that is, if and only if it has no Garden of Eden configuration. An automaton that is both injective and surjective is called a reversible cellular automaton.

The Garden of Eden theorem, due to Edward F. Moore (1962) and John Myhill (1963), states that a cellular automaton in a Euclidean space is locally injective if and only if it is surjective. In other words, it states that a cellular automaton has a Garden of Eden, if and only if it has twins. More strongly, every non-locally-injective cellular automaton has an orphan pattern. An immediate corollary is that an injective cellular automaton must be surjective.

Proof sketch

The main idea of the proof of the theorem is to use a counting argument, to show that any failure of local injectivity (twin patterns) leads to an orphan pattern, and vice versa. In more detail, suppose for concreteness that the underlying lattice of the automaton is a two-dimensional square grid, that it has s different cell states, that the twin patterns P and Q that both fit into an n × n square, and that the radius of any cell's neighborhood is at most n. Then, in order to determine whether a pattern that fits within an mn × mn square is an orphan, one need only look at potential predecessors that fit within an (m + 2)n × (m + 2)mn square and that do not contain pattern Q. But there are only (s^{n × n} − 1)^{(m + 2) × (m + 2)} of these potential predecessors. For sufficiently large values of m this number is smaller than the number s^{mn × mn} of potential orphans. Therefore, one of the potential orphans has no predecessor and is really an orphan; that is, non-injectivity implies non-surjectivity. Conversely, an argument involving König's infinity lemma shows that any non-surjective rule must have an orphan, and (letting n be the size of a bounding box of this orphan) a very similar counting argument shows that the number of patterns that fit within an (m + 2)n × (m + 2)mn square and do not contain an orphan is too small to provide a distinct successor to every starting pattern within an mn × mn square, from which it follows that some two of the possible starting patterns are twins. Therefore, non-surjectivity implies local non-injectivity.

Limitations

The use of the infinity lemma in this proof of the Garden of Eden theorem makes it non-constructive, but this is unavoidable, because there cannot exist an algorithm that always terminates and that correctly tests whether a given automaton has a Garden of Eden.^[3]

The distinction between injectivity and local injectivity in the proof is also necessary, as there exist cellular automata that are locally injective but not injective. One example is Rule 90, the one-dimensional binary automaton that replaces each state with the exclusive or of its two neighbors; in this automaton, every state has four predecessors, so it is not injective but also has no Garden of Eden.^[4]

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.^[5] However, the Garden of Eden theorem can be generalized beyond Euclidean spaces, to cellular automata defined on the elements of an amenable group or a sofic group; the proof of this generalization uses the Ax–Grothendieck theorem, an analogous relation between injectivity and bijectivity in algebraic geometry.^[6]

With quiescent states

In automata such as Conway's Game of Life, there is a special "quiescent" state such that a quiescent cell whose neighborhood is entirely quiescent remains quiescent. In this case one may define a "finite configuration" to be a configuration with only finitely many non-quiescent cells. Any non-locally-injective cellular automaton with a quiescent state has Gardens of Eden that are themselves finite configurations, for instance any finite configuration that contains an orphan. It may also be possible for an automaton to have a finite configuration whose only predecessors are not finite (for instance, in Rule 90, a configuration with a single live cell has this property). However, the Garden of Eden theorem does not characterize the existence of such patterns.^[7]

In Conway's Game of Life itself, it is easy to find twin patterns: for instance, a 5 × 5 square of quiescent cells, and a square of the same size in which only the central square is alive, have the same effect on any surrounding configuration. Therefore, Conway's Game of Life is not locally injective, and the Garden of Eden theorem implies that it has a Garden of Eden configuration.

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 copies had found themselves in some variant of the "real world" after being terminated; 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.^[8]

Notes

1. ^ ^{a b} In Lifeline Vol. 3 (September 1971), editor Robert T. Wainwright announced that Roger Banks and Steve Ward had proven the existence of a Garden of Eden within a 9 × 33 rectangle, and presented a pattern believed by Banks to be a Garden of Eden. In Lifeline Vol. 4 (December 1971), Wainwright reported that a group at Honeywell using software by Don Woods had verified Banks' pattern to be a Garden of Eden. See also Gardner, Martin, Wheels, Life, and Other Mathematical Amusements, p. 248, http://maa.org/pubs/focus/Gardner_GameofLife10-1970.pdf .
2. ^ "Garden of Eden 5". LifeWiki. September 9, 2009. http://www.conwaylife.com/wiki/index.php?title=Garden_of_Eden_5. Retrieved 2009-09-09. 
3. ^ Kari (1990). Kari's main result is that it is undecidable to test whether a cellular automaton is reversible, but he also shows the undecidability of testing whether a Garden of Eden exists.
4. ^ Sutner, Klaus (1991), "De Bruijn Graphs and Linear Cellular Automata", Complex Systems 5: 19–30, http://www.complex-systems.com/pdf/05-1-3.pdf .
5. ^ Margenstern (2009). Margenstern credits the result jointly to himself and Jarkko Kari.
6. ^ Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), On algebraic cellular automata, arXiv:1011.4759 .
7. ^ Amoroso & Cooper (1970); Skyum (1975).
8. ^ Blackford, Russell; Ikin, Van; McMullen, Sean (1999), "Greg Egan", Strange constellations: a history of Australian science fiction, Contributions to the study of science fiction and fantasy, 80, Greenwood Publishing Group, pp. 190–200, ISBN 9780313251122 ; Hayles, N. Katherine (2005), "Subjective cosmology and the regime of computation: intermediation in Greg Egan's fiction", My mother was a computer: digital subjects and literary texts, University of Chicago Press, pp. 214–240, ISBN 9780226321479 .

References

• Amoroso, S.; Cooper, G. (1970), "The Garden-of-Eden theorem for finite configurations", Proceedings of the American Mathematical Society 26 (1): 158–164, doi:10.1090/S0002-9939-1970-0276007-5 .
• Hardouin-Duparc, J. (1972/73), "À la recherche du paradis perdu", Publ. Math. Univ. Bordeaux Année 4: 51–89 .
• Hardouin-Duparc, J. (1974), "Paradis terrestre dans l’automate cellulaire de Conway", Rev. Française Automat. Informat. Recherche Operationnelle Ser. Rouge 8 (R-3): 64–71 .
• Kari, Jarkko (1990), "Reversibility of 2D cellular automata is undecidable", Physica D 45: 379–385, doi:10.1016/0167-2789(90)90195-U .
• Margenstern, Maurice (2009), "About the Garden of Eden theorems for cellular automata in the hyperbolic plane", 15th International Workshop on Cellular Automata and Discrete Complex Systems, Electronic Notes in Theoretical Computer Science, 252, pp. 93–102, doi:10.1016/j.entcs.2009.09.016 .
• Moore, E. F. (1962), "Machine models of self-reproduction", Proc. Symp. Applied Mathematics 14: 17–33 . Reprinted in Burks, Arthur W. (1970), Essays on Cellular Automata, University of Illinois Press, pp. 187–203 .
• Myhill, J. (1963), "The converse of Moore's Garden-of-Eden theorem", Proceedings of the American Mathematical Society 14: 685–686, doi:10.2307/2034301 . Reprinted in Burks, Arthur W. (1970), Essays on Cellular Automata, University of Illinois Press, pp. 204–205 .
• Skyum, Sven (1975), "Confusion in the Garden of Eden", Proceedings of the American Mathematical Society 50 (1): 332–336, doi:10.1090/S0002-9939-1975-0386350-1 .

External links

• Garden of Eden, LifeWiki
• Garden of Eden (Eric Weisstein's Treasure Trove of The Game of Life)