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 injective 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 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.
The Garden of Eden theorem, due to Edward F. Moore (1962) and John Myhill (1963), states that a cellular automaton in a Euclidean space 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.
Read more about this topic: Garden Of Eden (cellular Automaton)
Famous quotes containing the words garden, eden and/or theorem:
“Or of the garden where we first mislaid
Simplicity of wish and will, forgetting
Out of what cognate splendor all things came
To take their scattering names;”
—Richard Wilbur (b. 1921)
“What is Africa to me:
Copper sun or scarlet sea,
Jungle star or jungle track,
Strong bronzed men, or regal black
Women from whose loins I sprang
When the birds of Eden sang?”
—Countee Cullen (1903–1946)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)