Garden of Eden (cellular automaton)
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] The Garden of Eden theorem
It often 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.
[edit] Searching for the Garden of Eden
Jean Hardouin-Duparc (1972, 1974) pioneered a computational approach to finding orphan 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 orphans with that width.
The smallest known orphan pattern in Conway's Game of Life was found by Nicolay Beluchenko on September 6, 2009.[1] It has 69 living cells and fits in an 11x11 rectangle.
[edit] 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.
[edit] See also
[edit] External links
[edit] Notes
- ^ "Garden of Eden 5". LifeWiki. September 9, 2009. http://www.conwaylife.com/wiki/index.php?title=Garden_of_Eden_5. Retrieved 2009-09-09.
[edit] References
- Hardouin-Duparc, J. (1972/73). "À la recherche du paradis perdu". Publ. Math. Univ. Bordeaux Année 4: 51–89.
- Hardouin-Duparc, J. (1974). "Paradis terrestre dans l’automate cellulaire de Conway". Rev. Française Automat. Informat. Recherche Operationnelle Ser. Rouge 8 (R-3): 64–71.
- Moore, E. F. (1962). "Machine models of self-reproduction". Proc. Symp. Applied Mathematics 14: 17–33.
- Myhill, J. (1963). "The converse of Moore's Garden-of-Eden theorem". Proceedings of the American Mathematical Society 14: 685–686. doi:.
|
||||||||||||||||||||
