Garden of Eden (cellular automaton)
John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.
For one-dimensional cellular automata, orphans and Gardens of Eden can be found by an efficient algorithm, but for higher dimensions this is an undecidable problem.
Nevertheless, computer searches have succeeded in finding these patterns in Conway's Game of Life.
The Garden of Eden theorem of Moore and Myhill asserts that a cellular automaton on the square grid, or on a tiling of any higher dimensional Euclidean space, has a Garden of Eden if and only if it has twins, two finite patterns that have the same successors whenever one is substituted for the other.
[6] For one-dimensional cellular automata, Gardens of Eden can be found by an efficient algorithm whose running time is 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.
[7] 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.
[8] 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.
[10] 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.
[12] In a cellular automaton, two finite patterns are twins if one can be substituted for the other wherever it appears, without changing future configurations.
[3] The Garden of Eden theorem, due to Edward F. Moore (1962) and John Myhill (1963), asserts that a cellular automaton in a Euclidean space is locally injective if and only if it is surjective.
[15] In the case of Conway's Game of Life, twins are much easier to find than orphans.
[18] 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.
[19] However, the Garden of Eden theorem can be generalized beyond Euclidean spaces, to cellular automata defined on the elements of an amenable group.
[20] 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.
[23] 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.
