Garden of Eden

A Garden of Eden (briefly, GoE)for a cellular automaton$𝒜=⟨Q,𝒩,f⟩$on a group $G$is a configuration $c\in Q^G$which is not in the image of the global function $F_{𝒜}$ of $𝒜$.

In other words, a Garden of Eden is a global situationwhich can be started from, but never returned to.

The finitary counterpart of a GoE configurationis an orphan pattern:a pattern which cannot be obtainedby synchronous application of the local function $f$.

Of course,any cellular automaton with an orphan patternalso has a GoE configuration.

Lemma 1 (Orphan pattern principle)

If a cellular automaton with finite set of states $Q$has a GoE configuration,then it also has an orphan pattern.

Proof.First, suppose that $G$ is countable.Let$𝒜=⟨Q,𝒩,f⟩$be a cellular automaton with no orphan pattern.Let $c:G\to Q$ be a configuration:we will prove that there is some $e:G\to Q$such that $F_{𝒜}(e)=c$.

Let$G={\{g_n\}}_{n\ge 0}$be an enumeration of $G$:put $E_n=\{g_i\mid i\le n\}$and let $p_n:E_n\to Q$ be defined as$p_n={c|}_{E_n}.$By hypothesis, none of the $p_n$’s is an orphan,so there is a sequence of configurations$c_n:G\to Q$satisfying${F_{𝒜}(c_n)|}_{E_n}=p_n={c|}_{E_n}.$It is easy to see that${lim}_{k\to \mathrm{\infty }}{F}_{𝒜}(c_{n_k})=c.$But if $Q$ is finite,then $Q^G$ is compact by Tychonoff’s theorem,so there exista a subsequence${\{c_{n_k}\}}_{k\ge 0}$and a configuration $e:G\to Q$ satisfying${lim}_{k\to \mathrm{\infty }}{c}_{n_k}=e:$Since $F_{𝒜}$ is continuous in the product topology, $F(e)=c$.

Let now $G$ be arbitrary.Let $H$ be the subgroup generated by the neighborhood index $𝒩$:since $𝒩$ is finite, $H$ is countable.Let $J$ be a set of representatives of the left cosets of $H$ in $G$,so that$G={\bigsqcup }_{j\in J}jH.$(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:G\to Q$ be a Garden of Eden configuration for $𝒜$:then at least one of the configurations$c_j(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 $𝒜$. $\mathrm{\square }$