Garden of Eden (cellular automata)

In a cellular automaton, a Garden of Eden configuration is a configuration which 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 one- or two-dimensional infinite square lattice). Each Garden of Eden configuration contains at least one finite pattern with no predecessor. 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.

The Garden of Eden theorem

It often so happens that a cellular automaton has a designated cell state called blank, or quiescent.In that case, a finite configuration refers to one on which there are only finite number of non-blank cells. A cellular automaton is injective over finite configurations if it maps different finite configurations into different configurations.

By definition, a cellular automaton is surjective (i.e., its global mapping is onto), if and only if it has no Garden of Eden configuration.The Garden of Eden theorem, due to Edward F. Moore and John Myhill,states that the class of surjective cellular automata and those which are injective over finite configurations coincide. In other words, it states that a cellular automaton has a Garden of Eden, if and only if it has two different finite configurations that evolve into the same configuration in one step.

As a corollary, every injective cellular automaton (i.e., one with one-to-one global mapping) is surjective, hence also bijective. However, note that surjective cellular automata do not need to be injective.

For example, in the Game of Life, it is easy to find two different finite configurations (i.e., configurations with finitely many alive cells) which are mapped into the same configuration: The configuration in which every cell is dead, and the one in which exactly one cell is alive both lead to the one in which every cell is dead. The Garden of Eden theorem then implies that there must exist an orphan pattern, hence also a Garden of Eden configuration.

Searching for the Garden of Eden

Jean Hardouin-Duparc (1972, 1974) pioneered a computational approach to finding Garden of Eden patterns, involving the construction of the complement of the language accepted by a nondeterministic finite state machine. This machine recognizes in a row-by-row fashion patterns (with a fixed width) that have predecessors, so its complement is a regular language describing all Gardens of Eden with that width.

The smallest known Garden of Eden pattern was found by Achim Flammenkamp on June 23, 2004 [http://www.uni-bielefeld.de/~achim/orphan_2nd.html] . It has 72 living cells and fits in a 12x11 rectangle.

In fiction

In Greg Egan's novel "Permutation City", the concept of a "Garden of Eden configuration" in a cellular automaton is important to the metaphysics described in the book.

See also

* Garden of Eden theorem
* Surjective cellular automaton
* Pre-injective cellular automaton
* Reversible cellular automaton

External links

* [http://www.ericweisstein.com/encyclopedias/life/GardenofEden.html Garden of Eden (Eric Weisstein's Treasure Trove of The Game of Life)]

References

*cite journal
author = Hardouin-Duparc, J.
title = À la recherche du paradis perdu
journal = Publ. Math. Univ. Bordeaux Année
volume = 4
pages = 51–89
year = 1972/73

*cite journal
author = Hardouin-Duparc, 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

*cite journal
authorlink = Edward F. Moore
author = Moore, E. F.
title = Machine models of self-reproduction
journal = Proc. Symp. Applied Mathematics
volume = 14
year = 1962
pages = 17–33

*cite journal
authorlink = John Myhill
author = Myhill, J.
title = The converse of Moore's Garden-of-Eden theorem
journal = Proceedings of the American Mathematical Society
volume = 14
year = 1963
pages = 685–686 | doi = 10.2307/2034301