Garden of Eden

A Garden of Eden (briefly, GoE) for a cellular automatonMathworldPlanetmath 𝒜=Q,𝒩,f on a group G is a configurationMathworldPlanetmathPlanetmath cQG which is not in the image of the global function F𝒜 of 𝒜.

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 f.

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 setMathworldPlanetmath of states Q has a GoE configuration, then it also has an orphan pattern.

Proof. First, suppose that G is countableMathworldPlanetmath. Let 𝒜=Q,𝒩,f be a cellular automaton with no orphan pattern. Let c:GQ be a configuration: we will prove that there is some e:GQ such that F𝒜(e)=c.

Let G={gn}n0 be an enumeration of G: put En={giin} and let pn:EnQ be defined as pn=c|En. By hypothesisMathworldPlanetmath, none of the pn’s is an orphan, so there is a sequenceMathworldPlanetmath of configurations cn:GQ satisfying F𝒜(cn)|En=pn=c|En. It is easy to see that limkF𝒜(cnk)=c. But if Q is finite, then QG is compact by Tychonoff’s theorem, so there exista a subsequence {cnk}k0 and a configuration e:GQ satisfying limkcnk=e: Since F𝒜 is continuous in the product topology, F(e)=c.

Let now G be arbitrary. Let H be the subgroupMathworldPlanetmathPlanetmath generated by the neighborhoodMathworldPlanetmath index 𝒩: since 𝒩 is finite, H is countable. Let J be a set of representatives of the left cosetsMathworldPlanetmath of H in G, so that G=jJjH. (Observe that we do not require that H is normal in G.) Call 𝒜H the cellular automaton on H that has the same local description (set of states, neighborhood index, local function) as 𝒜. Let c:GQ be a Garden of Eden configuration for 𝒜: then at least one of the configurations cj(h)=c(jh) must be a Garden of Eden for 𝒜H. By the discussion above, 𝒜H must have an orphan pattern, which is also an orphan pattern for 𝒜.

Title Garden of Eden
Canonical name GardenOfEden
Date of creation 2013-03-22 19:22:01
Last modified on 2013-03-22 19:22:01
Owner Ziosilvio (18733)
Last modified by Ziosilvio (18733)
Numerical id 6
Author Ziosilvio (18733)
Entry type Definition
Classification msc 37B15
Classification msc 68Q80
Defines orphan pattern (cellular automaton)
Defines orphan pattern principle