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:
“When I go into my garden with a spade, and dig a bed, I feel such an exhilaration and health, that I discover that I have been defrauding myself all this time in letting others do for me what I should have done with my own hands.”
—Ralph Waldo Emerson (1803–1882)
“The Marxist vision of man without God must eventually be seen as an empty and a false faith—the second oldest in the world—first proclaimed in the Garden of Eden with whispered words of temptation: “Ye shall be as gods.””
—Ronald Reagan (b. 1911)
“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)