View source for Garden of Eden (cellular automaton)

{{short description|Pattern that has no predecessors}}
{{good article}}
[[Image:Garden of Eden pattern.png|thumb|upright=1.35|A Garden of Eden in [[Conway's Game of Life]], discovered by R. Banks in 1971.<ref name="banks"/> The cells outside the image are all dead (white).]]
[[Image:Garden of Eden 4.png|thumb|right|An orphan in Life found by Achim Flammenkamp. Black squares are required live cells; blue x's are required dead cells.]]

In a [[cellular automaton]], a '''Garden of Eden''' is a configuration that has no predecessor. It can be the [[initial condition|initial configuration]] of the automaton but cannot arise in any other way.
[[John Tukey]] named these configurations after the [[Garden of Eden]] in [[Abrahamic religions]], which was created out of nowhere.{{sfnp|Moore|1962}}

A Garden of Eden is determined by the state of every cell in the automaton (usually a one- or two-dimensional infinite [[square lattice]] of cells). However, for any Garden of Eden there is a finite pattern (a subset of cells and their states, called an ''orphan'') with the same property of having no predecessor, no matter how the remaining cells are filled in.
A configuration of the whole automaton is a Garden of Eden if and only if it contains an orphan.
For one-dimensional cellular automata, orphans and Gardens of Eden can be found by an efficient algorithm, but for higher [[dimension]]s 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 [[Edward F. Moore|Moore]] and [[John Myhill|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.

==Definitions==
A [[cellular automaton]] is defined by a grid of cells, a finite set of states that can be assigned to each cell, and an update rule.
Often, the grid of cells is the one- or two-dimensional infinite [[square lattice]]. The update rule determines the next state of each cell as a function of its current state and of the current states of certain other nearby cells (the ''neighborhood'' of the cell).
The neighborhood can be an arbitrary finite set of cells, but each two cells should have neighbors in the same relative positions and all cells must use the same update rule.
A ''configuration'' of the automaton is an assignment of a state to every cell.<ref name="kari-defs">{{harvtxt|Kari|2012}}, Section 2.1, "Basic Definitions", pp.&nbsp;5–6.</ref>

The ''successor'' of a configuration is another configuration, formed by applying the update rule simultaneously to every cell.<ref name="succpred">{{harvtxt|Toffoli|Margolus|1990}}. Note however that Toffoli and Margolus refer to the transition function as the global map.</ref>
The ''transition function'' of the automaton is the function that maps each configuration to its successor.<ref name="kari-defs"/><!-- Only sources trans func, not succ or pred -->
If the successor of configuration ''X'' is configuration ''Y'', then ''X'' is a ''predecessor'' of ''Y''.
A configuration may have zero, one, or more predecessors, but it always has exactly one successor.<ref name="succpred"/>
A Garden of Eden is defined to be a configuration with zero predecessors.<ref>{{harvtxt|Kari|2012}}, p.&nbsp;10.</ref>

A ''pattern'', for a given cellular automaton, consists of a finite set of cells together with a state for each of those cells.<ref name="kari-pattern">{{harvtxt|Kari|2012}}, p.&nbsp;11.</ref> 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.<ref name="kari-pattern"/><!-- sources orphan def but not def of predecessor of a pattern -->

== Searching for the Garden of Eden ==
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.<ref name="undecidable">{{harvtxt|Kari|1990}}; {{harvtxt|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.</ref> 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.<ref>{{harvtxt|Toffoli|Margolus|1990}}: "Even if one were willing to fall back on a brute-force search, a long search time would generate only a few items, and even those would be for the most part quite uninteresting."</ref>

{{harvs|first=Jean|last=Hardouin-Duparc|year=1972–73|year2=1974|txt}} pioneered a more efficient computational approach for finding orphan patterns. His method is based on the theory of [[formal language]]s, 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 [[complement (set theory)|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.{{sfnp|Hardouin-Duparc|1972–73}}

[[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 {{math|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.<ref name="banks">In ''Lifeline'' [http://www.conwaylife.com/wiki/index.php?title=Lifeline_Volume_3 Vol. 3] (September 1971), editor Robert T. Wainwright announced that Roger Banks and Steve Ward had proven the existence of a Garden of Eden whose live cells fit into a {{math|9 × 33}} rectangle, and presented a configuration believed by Banks to be a Garden of Eden. In ''Lifeline'' [http://www.conwaylife.com/wiki/index.php?title=Lifeline_Volume_4 Vol. 4] (December 1971), Wainwright reported that a group at [[Honeywell]] using software by [[Don Woods (programmer)|Don Woods]] had verified Banks' configuration to be a Garden of Eden. See also {{harvtxt|Gardner|1983}}.</ref>
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.{{sfnp|Hardouin-Duparc|1974}}

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.{{sfnp|Flammenkamp|2016}}

==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.<ref name="kari-orphan"/><ref>The one-dimensional case of this result is Theorem 5.1 of {{harvtxt|Hedlund|1969}}. As in the simpler proof given here, it uses compactness of the configuration space. In their earlier work, Moore and Myhill did not distinguish orphans from Gardens of Eden, and proved their results only in terms of orphans.</ref>
To prove this, Kari<ref name="kari-orphan">{{harvtxt|Kari|2012}}, Proposition 2, p.&nbsp;11.</ref> 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 function]]s on the space of configurations.<ref>{{harvtxt|Hedlund|1969}}, Theorem 3.4.</ref> 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]].<ref name="kari-orphan"/>

For each finite pattern, the set of configurations that contain the pattern is an [[open set]] in this topology, called a ''cylinder''.<ref name="kari-pattern"/> The cylinders form a [[Base (topology)|basis]] for the topology.
As Kari observes, the collection of configurations that are not Gardens of Eden is just the image of the transition function, so by the [[closed map lemma]] for compact spaces it is a [[closed set]]. The set of Gardens of Eden, correspondingly, is an open set. Because it is open and the cylinders form a basis, the set of Gardens of Eden can be represented as a union of cylinders.
Each of the cylinders in this union consists only of Gardens of Eden, so the pattern that determines each cylinder must be an orphan. If the set of Gardens of Eden is non-empty, there must be at least one cylinder in this union, so there must be at least one orphan. And any particular Garden of Eden must belong to one of these cylinders, and therefore must contain the orphan for that cylinder.<ref name="kari-orphan"/>

== The Garden of Eden theorem<!--'Garden of Eden theorem' redirects here--> ==
In a cellular automaton, two finite patterns are ''twins'' if one can be substituted for the other wherever it appears, without changing future configurations. A cellular automaton is [[injective function|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 function|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]].<ref name="kari-defs"/>

The '''Garden of Eden theorem'''<!--boldface per WP:R#PLA-->, due to {{harvs|first=Edward F.|last=Moore|authorlink=Edward F. Moore|year=1962|txt}} and {{harvs|first=John|last=Myhill|authorlink=John Myhill|year=1963|txt}}, asserts that a cellular automaton in a [[Euclidean space]] is locally injective if and only if it is surjective. In other words, it asserts 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. Moore proved one direction of the theorem, that automata with twins have orphans;{{sfnp|Moore|1962}} Myhill proved the converse, that an automaton with an orphan also has twins.{{sfnp|Myhill|1963}}

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 configurations 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.{{sfnp|Gardner|1983}}

===Proof sketch===
The main idea of the proof of the theorem is to use a [[combinatorial proof|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 {{math|''s''}} different cell states, that the twin patterns {{math|''P''}} and {{math|''Q''}} both fit into an {{math|''n'' × ''n''}} square, and that the radius of any cell's neighborhood is at most {{math|''n''}}. Then, in order to determine whether a pattern that fits within an {{math|''mn'' × ''mn''}} square is an orphan, one need only look at the parts of potential predecessors that fit within an {{math|(''m'' + 2)''n'' × (''m'' + 2)''n''}} square and that do not contain pattern {{math|''Q''}}. But there are only
{{math|(''s''<sup>''n'' × ''n''</sup> &minus; 1)<sup>(''m'' + 2) × (''m'' + 2)</sup>}} of these potential predecessors. For sufficiently large values of {{math|''m''}} this number is smaller than the number {{math|''s''<sup>''mn'' × ''mn''</sup>}} 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 (letting {{math|''n''}} be the size of a [[bounding box]] of an orphan) a very similar counting argument shows that the number of patterns that fit within an {{math|(''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 {{math|''mn'' × ''mn''}} square, from which it follows that some two of the possible starting patterns are twins. Therefore, non-surjectivity implies local non-injectivity.{{sfnp|Myhill|1963}}

===Injectivity versus local injectivity===
[[File:Rule90rand-expanded.png|thumb|upright=0.75|Time-space diagram of [[Rule 90]], which has no Garden of Eden despite being non-injective. Each row depicts a configuration, with time progressing downwards.]]
The distinction between injectivity and local injectivity in the theorem is necessary, as there exist cellular automata that are locally injective but not injective. One example is [[Rule 90]], the one-dimensional binary automaton whose update rule replaces each cell's 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.{{sfnp|Sutner|1991}}

===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.<ref>{{harvtxt|Amoroso|Cooper|1970}}; {{harvtxt|Skyum|1975}}.</ref>

===In non-Euclidean geometries===
In cellular automata defined over tessellations of the [[Hyperbolic space|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 tilings in hyperbolic plane|uniform hyperbolic tilings]] in which three [[heptagon]]s meet at each vertex, or in which four [[pentagon]]s meet at each vertex.<ref>{{harvtxt|Margenstern|2009}}. Margenstern credits the result jointly to himself and [[Jarkko Kari]].</ref>

However, the Garden of Eden theorem can be generalized beyond Euclidean spaces, to cellular automata defined on the elements of an [[amenable group]].<ref>{{harvtxt|Ceccherini-Silberstein|Machì| Scarabotti|1999}}; {{harvtxt|Capobianco|Guillon|Kari|2013}}; {{harvtxt|Bartholdi2019}}.</ref> A weaker form of the Garden of Eden theorem asserts that every injective cellular automaton is surjective. It can be proven for [[sofic group]]s using the [[Ax–Grothendieck theorem]], an analogous relation between injectivity and bijectivity in algebraic geometry.{{sfnp|Gromov|1999}} More generally, the groups for which this weaker form holds are called [[surjunctive group]]s.{{sfnp|Gottschalk|1973}} There are no known examples of groups that are not surjunctive.{{sfnp|Ceccherini-Silberstein|Coornaert|2010}}

== 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.<ref>{{harvtxt|Blackford|Ikin|McMullen|1999}}; {{harvtxt|Hayles|2005}}.</ref>

== Notes ==
{{reflist|30em}}

== References ==
{{refbegin|30em}}
*{{citation|first1=S.|last1=Amoroso|first2=G.|last2=Cooper|title=The Garden-of-Eden theorem for finite configurations|journal=[[Proceedings of the American Mathematical Society]]|volume=26|issue=1|pages=158–164|year=1970|doi=10.1090/S0002-9939-1970-0276007-5|doi-access=free}}
*{{citation
 | last = Bartholdi | first = Laurent
 | others = with an appendix by Dawid Kielak
 | arxiv = 1605.09133
 | doi = 10.4171/JEMS/900
 | issue = 10
 | journal = Journal of the European Mathematical Society 
 | mr = 3994103
 | pages = 3191–3197
 | title = Amenability of groups is characterized by Myhill's theorem
 | volume = 21
 | year = 2019}}
*{{citation
 | last1 = Blackford
 | first1 = Russell
 | last2 = Ikin
 | first2 = Van
 | last3 = McMullen
 | first3 = Sean
 | contribution = Greg Egan
 | isbn = 978-0-313-25112-2
 | pages = [https://archive.org/details/strangeconstella0000blac/page/190 190–200]
 | publisher = Greenwood Publishing Group
 | series = Contributions to the study of science fiction and fantasy
 | title = Strange constellations: a history of Australian science fiction
 | volume = 80
 | year = 1999
 | url-access = registration
 | url = https://archive.org/details/strangeconstella0000blac/page/190
 }}
*{{citation
 | last1 = Capobianco | first1 = Silvio
 | last2 = Guillon | first2 = Pierre
 | last3 = Kari | first3 = Jarkko | author3-link = Jarkko Kari
 | issue = 3
 | journal = Discrete Mathematics & Theoretical Computer Science
 | mr = 3141826
 | pages = 41–60
 | title = Surjective cellular automata far from the Garden of Eden
 | url = https://hal.inria.fr/hal-00966380/
 | volume = 15
 | year = 2013}}
*{{citation
 | last1 = Ceccherini-Silberstein | first1 = Tullio
 | last2 = Coornaert | first2 = Michel
 | contribution = Surjunctive groups
 | doi = 10.1007/978-3-642-14034-1_3
 | isbn = 978-3-642-14033-4
 | mr = 2683112
 | pages = 57–75
 | publisher = [[Springer-Verlag]]
 | series = Springer Monographs in Mathematics
 | title = Cellular automata and groups
 | year = 2010}}
*{{citation
 | last1 = Ceccherini-Silberstein | first1 = T. G.
 | last2 = Machì | first2 = A.
 | last3 = Scarabotti | first3 = F.
 | issue = 2
 | journal =  Annales de l'Institut Fourier
 | mr = 1697376
 | pages = 673–685
 | title = Amenable groups and cellular automata
 | url = http://www.numdam.org/item?id=AIF_1999__49_2_673_0
 | volume = 49
 | year = 1999 | doi=10.5802/aif.1686| doi-access = free
 }}
*{{citation
 | last = Flammenkamp | first = Achim
 | contribution = Garden of Eden / Orphan
 | contribution-url = https://wwwhomes.uni-bielefeld.de/achim/orphan_9th.html
 | date = April 2016
 | title = Achim's Game of Life Page
 | url = http://wwwhomes.uni-bielefeld.de/achim/gol.html}}
*{{citation
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | contribution = Chapters 20 and 21: The Game of Life, Parts I and II
 | contribution-url = https://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_GameofLife10-1970.pdf
 | pages = 214–258
 | publisher = W. H. Freeman
 | title = [[Wheels, Life, and Other Mathematical Amusements]]
 | year = 1983}}; see in particular pp.&nbsp;230 and 248
*{{citation
 | last = Gottschalk | first = Walter
 | contribution = Some general dynamical notions
 | doi = 10.1007/BFb0061728
 | mr = 0407821
 | pages = 120–125
 | publisher = [[Springer-Verlag]]
 | series = Lecture Notes in Mathematics
 | title = Recent Advances in Topological Dynamics (Proc. Conf. Topological Dynamics, Yale Univ., New Haven, Conn., 1972; in honor of Gustav Arnold Hedlund)
 | volume = 318
 | year = 1973| isbn = 978-3-540-06187-8
 }}
*{{citation
 | last = Gromov | first = M. | authorlink = Mikhail Leonidovich Gromov
 | doi = 10.1007/PL00011162
 | issue = 2
 | journal = [[Journal of the European Mathematical Society]]
 | mr = 1694588 | zbl=0998.14001 
 | pages = 109–197
 | title = Endomorphisms of symbolic algebraic varieties
 | volume = 1
 | year = 1999| doi-access = free
 }}
*{{citation
 | last = Hardouin-Duparc | first = J.
 | title = À la recherche du paradis perdu
 | journal = Publ. Math. Univ. Bordeaux Année
 | volume = 4
 | pages = 51–89
 | year = 1972–73}}
*{{citation
 | last = Hardouin-Duparc | first = J.
 | title = Paradis terrestre dans l'automate cellulaire de Conway
 | journal = Rev. Française Automat. Informat. Recherche Operationnelle Ser. Rouge
 | volume = 8
 | issue = R-3
 | pages = 64–71
 | year = 1974}}
*{{citation
 | last1 = Hartman | first1 = Christiaan
 | last2 = Heule | first2 = Marijn J. H. |author2-link= Marijn Heule
 | last3 = Kwekkeboom | first3 = Kees
 | last4 = Noels | first4 = Alain
 | issue = 3
 | journal = [[Electronic Journal of Combinatorics]]
 | mr = 3104514
 | page = P16
 | title = Symmetry in Gardens of Eden
 | volume = 20
 | year = 2013| doi = 10.37236/2611
 | doi-access = free
 }}
*{{citation
 | last = Hayles | first = N. Katherine
 | contribution = Subjective cosmology and the regime of computation: intermediation in Greg Egan's fiction
 | isbn = 978-0-226-32147-9
 | pages = 214–240
 | publisher = University of Chicago Press
 | title = My mother was a computer: digital subjects and literary texts
 | year = 2005}}
*{{citation
 | last = Hedlund | first = G. A. | author-link = Gustav A. Hedlund
 | doi = 10.1007/BF01691062
 | issue = 4
 | journal = Mathematical Systems Theory
 | pages = 320–375
 | title = Endomorphisms and Automorphisms of the Shift Dynamical Systems
 | volume = 3
 | year = 1969| s2cid = 21803927 }}
*{{citation
 | last = Kari | first = Jarkko | author-link = Jarkko Kari
 | doi = 10.1016/0167-2789(90)90195-U
 | journal = Physica D
 | pages = 379–385
 | title = Reversibility of 2D cellular automata is undecidable
 | volume = 45
 | issue = 1–3 | year = 1990| bibcode = 1990PhyD...45..379K }}
*{{citation
 | last = Kari | first = Jarkko |authorlink=Jarkko Kari
 | doi = 10.1016/S0022-0000(05)80025-X
 | issue = 1
 | journal = Journal of Computer and System Sciences
 | mr = 1259654
 | pages = 149–182
 | title = Reversibility and surjectivity problems of cellular automata
 | volume = 48
 | year = 1994| doi-access = free
 }}
*{{citation
 | last = Kari | first = Jarkko J. |authorlink=Jarkko Kari
 | editor1-last = Rozenberg | editor1-first = Grzegorz
 | editor2-last = Bäck | editor2-first = Thomas
 | editor3-last = Kok | editor3-first = Joost N.
 | contribution = Basic Concepts of Cellular Automata
 | doi = 10.1007/978-3-540-92910-9_1
 | pages = 3–24
 | publisher = Springer
 | title = Handbook of Natural Computing
 | year = 2012| isbn = 978-3-540-92909-3 }}
*{{citation
 | last = Margenstern | first = Maurice
 | contribution = About the Garden of Eden theorems for cellular automata in the hyperbolic plane
 | doi = 10.1016/j.entcs.2009.09.016
 | pages = 93–102
 | series = Electronic Notes in Theoretical Computer Science
 | title = 15th International Workshop on Cellular Automata and Discrete Complex Systems
 | volume = 252
 | year = 2009| doi-access = free
 }}
*{{citation
 | authorlink = Edward F. Moore
 | last = Moore | first = E. F.
 
 | title = Mathematical Problems in the Biological Sciences | chapter = Machines models of self-reproduction | series = Proceedings of Symposia in Applied Mathematics | volume = 14
 | year = 1962
 | pages = 17–33| doi = 10.1090/psapm/014/9961 | isbn = 9780821813140 }}; reprinted in {{citation|first=Arthur W.|last=Burks|authorlink=Arthur Burks|title=Essays on Cellular Automata|publisher=University of Illinois Press|year=1970|pages=187–203}}.
*{{citation
 | authorlink = John Myhill
 | last = Myhill | first = J.
 | title = The converse of Moore's Garden-of-Eden theorem
 | journal = [[Proceedings of the American Mathematical Society]]
 | volume = 14
 | year = 1963
 | issue = 4 | pages = 685–686 | doi = 10.1090/S0002-9939-1963-0155764-9 | doi-access=free| jstor = 2034301 }}; reprinted in {{citation|first=Arthur W.|last=Burks|authorlink=Arthur Burks|title=Essays on Cellular Automata|publisher=University of Illinois Press|year=1970|pages=204–205}}.
*{{citation
 | last = Skyum | first = Sven
 | doi = 10.1090/S0002-9939-1975-0386350-1
 | issue = 1
 | journal = Proceedings of the American Mathematical Society
 | pages = 332–336
 | title = Confusion in the Garden of Eden
 | volume = 50
 | year = 1975| doi-access = free
 }}
*{{citation
 | last = Sutner | first = Klaus
 | journal = Complex Systems
 | mr = 1116419
 | pages = 19–30
 | title = De Bruijn graphs and linear cellular automata
 | url = https://www.complex-systems.com/pdf/05-1-3.pdf
 | volume = 5
 | year = 1991}}
*{{citation
 | last1 = Toffoli | first1 = Tommaso | author1-link = Tommaso Toffoli
 | last2 = Margolus | first2 = Norman | author2-link = Norman Margolus
 | doi = 10.1016/0167-2789(90)90185-R
 | issue = 1–3
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | mr = 1094877
 | pages = 229–253
 | title = Invertible cellular automata: a review
 | volume = 45
 | year = 1990| bibcode = 1990PhyD...45..229T }}
{{refend}}

== External links ==
* [https://www.conwaylife.com/wiki/Garden_of_Eden Garden of Eden on LifeWiki]
* [http://www.ericweisstein.com/encyclopedias/life/GardenofEden.html Garden of Eden (Eric Weisstein's Treasure Trove of The Game of Life)] {{Webarchive|url=https://web.archive.org/web/20090106172121/http://www.ericweisstein.com/encyclopedias/life/GardenofEden.html |date=2009-01-06 }}

{{Conway's Game of Life}}

{{DEFAULTSORT:Garden Of Eden (Cellular Automaton)}}
[[Category:Cellular automaton patterns]]
[[Category:Garden of Eden]]