Garden of Eden pattern

From Wikipedia, the free encyclopedia

A Garden of Eden pattern, discovered by R. Banks in 1971, the first such pattern discovered in Conway's Game of Life.
A Garden of Eden pattern, discovered by R. Banks in 1971, the first such pattern discovered in Conway's Game of Life.
12x11 Garden of Eden pattern, currently the smallest known. Black squares are required ON cells; blue x's are required OFF cells.
12x11 Garden of Eden pattern, currently the smallest known. Black squares are required ON cells; blue x's are required OFF cells.

In the study of cellular automata, Garden of Eden patterns are configurations that cannot be reached from any other starting configuration. They are named after the biblical Garden of Eden because they have no predecessor configurations—they must be created as such.

According to Moore (1962), these configurations were named by John Tukey in the 1950s, long before John Conway invented his Game of Life.

Contents

[edit] The Garden of Eden theorem

Let some configuration at timestep t be denoted by Ct, and the function (the automaton) f to map the configuration Ct to Ct+1.

A Garden of Eden pattern Gt means that there does not exist any configuration Gt-1 such that f(Gt-1)=Gt. This means a cellular automaton which possesses Garden of Eden pattern(s) is not surjective.

One other characteristic of certain cellular automata is that of "reversibility", that is, given a configuration Ct, there is a unique predecessor configuration Ct-1. This condition implies that the automaton function is bijective. From the definition of bijectivity, cellular automata which possess Garden of Eden patterns are clearly not reversible. In fact, all non-injective automata possess Garden of Eden patterns: the Garden of Eden theorem, proved by Edward F. Moore and John Myhill, states that a cellular automaton is reversible if and only if it has no Garden of Eden pattern. Since the Game of Life is easily seen not to be reversible, it was known such patterns existed in it even before any were discovered.

[edit] 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 [1]. It has 72 living cells and fits in a 12x11 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] External links

[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:10.2307/2034301.