Garden of Eden pattern
Encyclopedia
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
, 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
Garden of Eden
The Garden of Eden is in the Bible's Book of Genesis as being the place where the first man, Adam, and his wife, Eve, lived after they were created by God. Literally, the Bible speaks about a garden in Eden...
in Abrahamic religions
Abrahamic religions
Abrahamic religions are the monotheistic faiths emphasizing and tracing their common origin to Abraham or recognizing a spiritual tradition identified with him...
, which was created out of nowhere, hence the name. According to , this name was coined by John Tukey
John Tukey
John Wilder Tukey ForMemRS was an American statistician.- Biography :Tukey was born in New Bedford, Massachusetts in 1915, and obtained a B.A. in 1936 and M.Sc. in 1937, in chemistry, from Brown University, before moving to Princeton University where he received a Ph.D...
in the 1950s.
A Garden of Eden is a configuration of the whole lattice (usually a one- or two-dimensional infinite square lattice
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. It is one of the five types of two-dimensional lattices as classified by their symmetry groups; its symmetry group is known symbolically as p4m.Two...
). 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.pioneered a more efficient computational approach for finding orphan patterns, based on the theory of formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s, 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
Nondeterministic finite state machine
In the automata theory, a nondeterministic finite state machine or nondeterministic finite automaton is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states...
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
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
, the patterns that do not have predecessors, by converting the nondeterministic finite state machine to a deterministic finite state machine
Deterministic finite state machine
In the theory of computation and automata theory, a deterministic finite state machine—also known as deterministic finite automaton —is a finite state machine accepting finite strings of symbols. For each state, there is a transition arrow leading out to a next state for each symbol...
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
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....
, 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 for predecessors.
Subsequently, Hardouin-Duparc used his formal language approach to find the narrowest possible Gardens of Eden in Conway's Game of Life
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....
, only six cells wide. The smallest known orphan pattern in Conway's Game of Life was found by Nicolay Beluchenko on September 6, 2009. 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 injectiveInjective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
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
Surjective function
In mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...
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
Reversible cellular automaton
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton and second-order cellular automaton methods...
.
The Garden of Eden theorem, due to and , states that a cellular automaton in a Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
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 argumentCombinatorial proof
In mathematics, the term combinatorial proof is often used to mean either of two types of proof of an identity in enumerative combinatorics that either states that two sets of combinatorial configurations, depending on one or more parameters, have the same number of elements , or gives a formula...
, 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 that 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 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, an argument involving König's infinity lemma
König's lemma
König's lemma or König's infinity lemma is a theorem in graph theory due to Dénes Kőnig . It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic,...
shows that any non-surjective rule must have an orphan, and (letting 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 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.
Limitations
The use of the infinity lemma in this proof of the Garden of Eden theorem makes it non-constructiveConstructivism (mathematics)
In the philosophy of mathematics, constructivism asserts that it is necessary to find a mathematical object to prove that it exists. When one assumes that an object does not exist and derives a contradiction from that assumption, one still has not found the object and therefore not proved its...
, but this is unavoidable, because there cannot exist an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that always terminates and that correctly tests whether a given automaton has a Garden of Eden.
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
Rule 90
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 a 1 value; in each time step all values are simultaneously replaced by the exclusive or of the two neighboring values...
, 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.
In cellular automata defined over tessellations of the hyperbolic plane
Hyperbolic space
In mathematics, hyperbolic space is a type of non-Euclidean geometry. Whereas spherical geometry has a constant positive curvature, hyperbolic geometry has a negative curvature: every point in hyperbolic space is a saddle point...
, 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
Uniform tilings in hyperbolic plane
There are an infinite number of uniform tilings on the hyperbolic plane based on the where 1/p + 1/q + 1/r ...
in which three heptagons meet at each vertex, or in which four pentagon
Pentagon
In geometry, a pentagon is any five-sided polygon. A pentagon may be simple or self-intersecting. The sum of the internal angles in a simple pentagon is 540°. A pentagram is an example of a self-intersecting pentagon.- Regular pentagons :In a regular pentagon, all sides are equal in length and...
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
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...
or a sofic group; the proof of this generalization uses the Ax–Grothendieck theorem, an analogous relation between injectivity and bijectivity in algebraic geometry.
With quiescent states
In automata such as Conway's Game of LifeConway'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....
, 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 Conway's Game of Life itself, it is easy to find twin patterns: for instance, a 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 EganGreg Egan
Greg Egan is an Australian science fiction author.Egan published his first work in 1983. He specialises in hard science fiction stories with mathematical and quantum ontology themes, including the nature of consciousness...
's novel Permutation City
Permutation City
Permutation City is a 1994 science fiction novel by Greg Egan that explores many concepts, including quantum ontology, via various philosophical aspects of artificial life and simulated reality. Sections of the story were adapted from Egan's 1992 short story "Dust" which dealt with many of the same...
, 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.