In a
cellular automaton
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
, a Garden of Eden is a configuration that has no predecessor. It can be the
initial configuration of the automaton but cannot arise in any other way.
John Tukey
John Wilder Tukey (; June 16, 1915 – July 26, 2000) was an American mathematician and statistician, best known for the development of the fast Fourier Transform (FFT) algorithm and box plot. The Tukey range test, the Tukey lambda distributi ...
named these configurations after the
Garden of Eden
In Abrahamic religions, the Garden of Eden ( he, גַּן־עֵדֶן, ) or Garden of God (, and גַן־אֱלֹהִים ''gan-Elohim''), also called the Terrestrial Paradise, is the Bible, biblical paradise described in Book of Genesis, Genes ...
in
Abrahamic religions
The Abrahamic religions are a group of religions centered around worship of the God of Abraham. Abraham, a Hebrew patriarch, is extensively mentioned throughout Abrahamic religious scriptures such as the Bible and the Quran.
Jewish tradition ...
, which was created out of nowhere.
A Garden of Eden is determined by the state of every cell in the automaton (usually a one- or two-dimensional infinite
square lattice
In mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice, denoted as . It is one of the five types of two-dimensional lattices as classified by their ...
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
In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
s this is an
undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
. Nevertheless, computer searches have succeeded in finding these patterns in
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further ...
.
The Garden of Eden theorem of
Moore
Moore may refer to:
People
* Moore (surname)
** List of people with surname Moore
* Moore Crosthwaite (1907–1989), a British diplomat and ambassador
* Moore Disney (1765–1846), a senior officer in the British Army
* Moore Powell (died c. 1573 ...
and
Myhill asserts that a cellular automaton on the square grid, or on a tiling of any higher dimensional
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
, 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
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
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
In mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice, denoted as . It is one of the five types of two-dimensional lattices as classified by their ...
. 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.
[, Section 2.1, "Basic Definitions", pp. 5–6.]
The ''successor'' of a configuration is another configuration, formed by applying the update rule simultaneously to every cell.
[. Note however that Toffoli and Margolus refer to the transition function as the global map.]
The ''transition function'' of the automaton is the function that maps each configuration to its successor.
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.
A Garden of Eden is defined to be a configuration with zero predecessors.
A ''pattern'', for a given cellular automaton, consists of a finite set of cells together with a state for each of those cells.
[, p. 11.] 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.
Searching for the Garden of Eden
For one-dimensional cellular automata, Gardens of Eden can be found by an efficient
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
, meaning that there is no algorithm that can be guaranteed to terminate and produce the correct answer.
[; . 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.] 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
In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...
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 language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
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
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state tr ...
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
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
by using the
powerset construction
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same f ...
, 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
Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writings of Lewis ...
credits
Alvy Ray Smith
Alvy Ray Smith III (born September 8, 1943) is an American computer scientist who co-founded Lucasfilm's Computer Division and Pixar, participating in the 1980s and 1990s expansion of computer animation into feature film.
Education
In 1965, A ...
with the observation that the Garden of Eden theorem applies to
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further ...
, 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
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
for predecessors.
[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 whose live cells fit into a rectangle, and presented a configuration believed by Banks to be a Garden of Eden. In ''Lifeline'
Vol. 4
(December 1971), Wainwright reported that a group at Honeywell
Honeywell International Inc. is an American publicly traded, multinational conglomerate corporation headquartered in Charlotte, North Carolina. It primarily operates in four areas of business: aerospace, building technologies, performance ma ...
using software by Don Woods Donald Woods (1933–2001) was a South African journalist and activist.
Donald or Don Woods may also refer to:
* Donald Woods (actor) (1906–1998), Canadian-born American film and television actor
* Donald Devereux Woods (1912–1964), British m ...
had verified Banks' configuration to be a Garden of Eden. See also .
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
In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure a ...
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
[, Proposition 2, p. 11.] uses a topological argument, based on the
Curtis–Hedlund–Lyndon theorem The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlun ...
according to which the transition functions of cellular automata are exactly the translation-invariant
continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
s on the space of configurations. Here, continuity is defined by assigning a
discrete topology
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are '' isolated'' from each other in a certain sense. The discrete topology is the finest to ...
to the finite set of states of the automaton, and then using a
product topology
In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seemin ...
with one term in the product for each cell in the automaton to construct a
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
whose points are the automaton's configurations. By
Tychonoff's theorem
In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov (whose surname sometimes is trans ...
it is a
compact space
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
.
For each finite pattern, the set of configurations that contain the pattern is an
open set
In mathematics, open sets are a generalization of open intervals in the real line.
In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are suf ...
in this topology, called a ''cylinder''.
The cylinders form a
basis
Basis may refer to:
Finance and accounting
*Adjusted basis, the net cost of an asset after adjusting for various tax-related items
*Basis point, 0.01%, often used in the context of interest rates
*Basis trading, a trading strategy consisting of ...
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
In mathematics, more specifically in topology, an open map is a function between two topological spaces that maps open sets to open sets.
That is, a function f : X \to Y is open if for any open set U in X, the image f(U) is open in Y.
Likewise, ...
for compact spaces it is a
closed set
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a cl ...
. 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.
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 configurations. A cellular automaton is
injective
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
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
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
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
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells s ...
.
The Garden of Eden theorem, due to and , asserts that a cellular automaton in a
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
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; Myhill proved the converse, that an automaton with an orphan also has twins.
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.
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 different cell states, that the twin patterns and both fit into an square, and that the radius of any cell's neighborhood is at most . Then, in order to determine whether a pattern that fits within an square is an orphan, one need only look at the parts of potential predecessors that fit within an square and that do not contain pattern . But there are only
of these potential predecessors. For sufficiently large values of this number is smaller than the number 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 be the size of a
bounding box
In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure a ...
of an orphan) a very similar counting argument shows that the number of patterns that fit within an square and do not contain an orphan is too small to provide a distinct successor to every starting pattern within an square, from which it follows that some two of the possible starting patterns are twins. Therefore, non-surjectivity implies local non-injectivity.
Injectivity versus local injectivity
![Rule90rand-expanded](https://upload.wikimedia.org/wikipedia/commons/e/e4/Rule90rand-expanded.png)
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
In the mathematics, mathematical study of cellular automaton, cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or ...
, the one-dimensional binary automaton whose update rule replaces each cell's state with the
exclusive or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
of its two neighbors. In this automaton, every state has four predecessors, so it is not injective but also has no Garden of Eden.
With quiescent states
In automata such as
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further ...
, 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.
In non-Euclidean geometries
In cellular automata defined over tessellations of the
hyperbolic plane
In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai– Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with:
:For any given line ''R'' and point ''P'' ...
, 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
heptagon
In geometry, a heptagon or septagon is a seven-sided polygon or 7-gon.
The heptagon is sometimes referred to as the septagon, using "sept-" (an elision of ''septua-'', a Latin-derived numerical prefix, rather than ''hepta-'', a Greek-derived num ...
s meet at each vertex, or in which four
pentagon
In geometry, a pentagon (from the Greek πέντε ''pente'' meaning ''five'' and γωνία ''gonia'' meaning ''angle'') is any five-sided polygon or 5-gon. The sum of the internal angles in a simple pentagon is 540°.
A pentagon may be simpl ...
s 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
In mathematics, an amenable group is a locally compact topological group ''G'' carrying a kind of averaging operation on bounded functions that is invariant under translation by group elements. The original definition, in terms of a finitely additi ...
. 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
In mathematics, the Ax–Grothendieck theorem is a result about injectivity and surjectivity of polynomials that was proved independently by James Ax and Alexander Grothendieck.
The theorem is often given as this special case: If ''P'' is an injec ...
, an analogous relation between injectivity and bijectivity in algebraic geometry. More generally, the groups for which this weaker form holds are called
surjunctive group
In mathematics, a surjunctive group is a group such that every injective cellular automaton with the group elements as its cells is also surjective. Surjunctive groups were introduced by . It is unknown whether every group is surjunctive.
Definit ...
s. There are no known examples of groups that are not surjunctive.
In fiction
In
Greg Egan
Greg Egan (born 20 August 1961) is an Australian science fiction writer and amateur mathematician, best known for his works of hard science fiction. Egan has won multiple awards including the John W. Campbell Memorial Award, the Hugo Award, an ...
's novel ''
Permutation City
''Permutation City'' is a 1994 science-fiction novel by Greg Egan that explores many concepts, including quantum ontology, through various philosophical aspects of artificial life and simulated reality. Sections of the story were adapted from E ...
'', 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 .
*
*
*
External links
Garden of Eden on LifeWiki
{{DEFAULTSORT:Garden Of Eden (Cellular Automaton)
Cellular automaton patterns
Garden of Eden