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:
“Paradise endangered: garden snakes and mice are appearing in the shadowy corners of Dutch Old Master paintings.”
—Mason Cooley (b. 1927)
“The new sound-sphere is global. It ripples at great speed across languages, ideologies, frontiers and races.... The economics of this musical esperanto is staggering. Rock and pop breed concentric worlds of fashion, setting and life-style. Popular music has brought with it sociologies of private and public manner, of group solidarity. The politics of Eden come loud.”
—George Steiner (b. 1929)
“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)