Garden of Eden
A Garden of Eden is a pattern that has no parents and thus can only occur in generation 0. The term was first used in connection with cellular automata by John W. Tukey, many years before Conway's Game of Life was conceived. It was known from the start that Gardens of Eden exist in Life because of a theorem by Edward Moore that guarantees their existence in a wide class of cellular automata.
Garden of Eden theorem
The Garden of Eden theorem was proved by Edward Moore and John Myhill pre-1970 and shows that a wide class of cellular automata must contain Garden of Eden patterns. Of particular interest is that Conway's Game of Life falls into this class, and thus Gardens of Eden were known to exist right from the the day it was conceived.
Statement of the theorem
A finite pattern (or finite configuration) is a pattern with a finite number of bits. A cellular automaton is said to be injective over finite patterns if no two distinct finite patterns map into the same finite pattern. It is said to be surjective if every pattern is mapped to by some other pattern. Thus, by definition a cellular automaton contains Gardens of Eden if and only if it is not surjective.
The Garden of Eden theorem states that the class of surjective cellular automata and those which are injective over finite configurations coincide. In other words, 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 and hence bijective. However, surjective cellular automata do not need to be injective.
Application to Conway's Game of Life
The theorem applies to Conway's Game of Life because it is easy to find two different finite patterns that 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 a Garden of Eden pattern.
Orphans
A related concept to Gardens of Eden is that of orphans, which are finite patterns that can not occur as part of the evolution of another pattern. That is, they are Gardens of Eden that can be extended in any way to perform other Gardens of Eden.
Examples
Several Gardens of Eden have been constructed, the first by Roger Banks et al. at MIT in 1971. In 1974 J. Hardouin-Duparc, et al. produced a 6 × 122 example.
External links
- Garden of Eden at the Life Lexicon