Garden of Eden
In other words, a Garden of Eden is a global situation which can be started from, but never returned to.
The finitary counterpart of a GoE configuration is an orphan pattern: a pattern which cannot be obtained by synchronous application of the local function .
Of course, any cellular automaton with an orphan pattern also has a GoE configuration.
Lemma 1 (Orphan pattern principle)
If a cellular automaton with finite set of states has a GoE configuration, then it also has an orphan pattern.
Proof. First, suppose that is countable. Let be a cellular automaton with no orphan pattern. Let be a configuration: we will prove that there is some such that .
Let be an enumeration of : put and let be defined as By hypothesis, none of the ’s is an orphan, so there is a sequence of configurations satisfying It is easy to see that But if is finite, then is compact by Tychonoff’s theorem, so there exista a subsequence and a configuration satisfying Since is continuous in the product topology, .
Let now be arbitrary. Let be the subgroup generated by the neighborhood index : since is finite, is countable. Let be a set of representatives of the left cosets of in , so that (Observe that we do not require that is normal in .) Call the cellular automaton on that has the same local description (set of states, neighborhood index, local function) as . Let be a Garden of Eden configuration for : then at least one of the configurations must be a Garden of Eden for . By the discussion above, must have an orphan pattern, which is also an orphan pattern for .
|Title||Garden of Eden|
|Date of creation||2013-03-22 19:22:01|
|Last modified on||2013-03-22 19:22:01|
|Last modified by||Ziosilvio (18733)|
|Defines||orphan pattern (cellular automaton)|
|Defines||orphan pattern principle|