Garden of Eden (cellular automaton)

A Garden of Eden 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

For one-dimensional cellular automata, Gardens of Eden can be found by an efficient algorithm (running in time polynomial in the size of the rule table of the automaton). For higher dimensions, determining whether a Garden of Eden exists is an undecidable problem, meaning that there is no algorithm that can be guaranteed to terminate and produce the correct answer.[2] 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 possible 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.

Jean Hardouin-Duparc (1972–73, 1974) 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 relatively straightforward 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 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 Marijn Heule, Christiaan Hartman, Kees Kwekkeboom and Alain Noels in December 2011.[3] It has 56 living cells and fits in an 10x10 square. To find this pattern, they made an assumption that the pattern to be found was symmetric (greatly reducing the search space) and used a Boolean satisfiability problem solver to test whether each candidate pattern was an orphan.[4]

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.

In the case of Conway's Game of Life, twins are much easier to find than orphans. For instance, a five-by-five block of dead cells and a five-by-five block with its center cell live and the remaining cells dead are twins: the state of the center cell cannot affect later states of the pattern. Thus, in this case, the Garden of Eden theorem allows the existence of a Garden of Eden to be demonstrated much more easily than by finding an explicit orphan pattern.

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 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)n square and that do not contain pattern Q. But there are only (sn × n − 1)(m + 2) × (m + 2) of these potential predecessors. For sufficiently large values of m this number is smaller than the number smn × 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)n 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 of two or more dimensions has a Garden of Eden.[2]

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.[5]

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.[6]

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.[7] A weaker form of the Garden of Eden theorem states that every injective cellular automaton is surjective; in this form, the theorem holds (by definition) for the cellular automata over every surjunctive group, and there are no known examples of groups that are not surjunctive.[8]

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.[9]

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.[10]

Notes

  1. 1 2 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 (PDF), p. 248.
  2. 1 2 Kari (1990); Kari (1994). 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.
  3. ↑ "Gardens of Eden". Game of Life News. January 14, 2012. Retrieved 2012-01-14.
  4. ↑ Hartman et al. (2013).
  5. ↑ Sutner, Klaus (1991), "De Bruijn Graphs and Linear Cellular Automata" (PDF), Complex Systems 5: 19–30.
  6. ↑ Margenstern (2009). Margenstern credits the result jointly to himself and Jarkko Kari.
  7. ↑ Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), On algebraic cellular automata, arXiv:1011.4759.
  8. ↑ Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), "Surjunctive groups", Cellular automata and groups, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, doi:10.1007/978-3-642-14034-1_3, ISBN 978-3-642-14033-4, MR 2683112
  9. ↑ Amoroso & Cooper (1970); Skyum (1975).
  10. ↑ 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 978-0-313-25112-2; 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 978-0-226-32147-9.

References

External links

This article is issued from Wikipedia - version of the Saturday, October 17, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.