# Garden of Eden

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

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

Proof. First, suppose that $G$ is countable. Let $\mathcal{A}=\langle Q,\mathcal{N},f\rangle$ 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_{\mathcal{A}}(e)=c$.

Let $G=\{g_{n}\}_{n\geq 0}$ be an enumeration of $G$: put $E_{n}=\{g_{i}\mid i\leq n\}$ and let $p_{n}:E_{n}\to Q$ be defined as $p_{n}=\left.{c}\right|_{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 $\left.{F_{\mathcal{A}}(c_{n})}\right|_{E_{n}}=p_{n}=\left.{c}\right|_{E_{n}}.$ It is easy to see that $\lim_{k\to\infty}F_{\mathcal{A}}(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\geq 0}$ and a configuration $e:G\to Q$ satisfying $\lim_{k\to\infty}c_{n_{k}}=e:$ Since $F_{\mathcal{A}}$ is continuous in the product topology, $F(e)=c$.

Let now $G$ be arbitrary. Let $H$ be the subgroup generated by the neighborhood index $\mathcal{N}$: since $\mathcal{N}$ 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 $\mathcal{A}_{H}$ the cellular automaton on $H$ that has the same local description (set of states, neighborhood index, local function) as $\mathcal{A}$. Let $c:G\to Q$ be a Garden of Eden configuration for $\mathcal{A}$: then at least one of the configurations $c_{j}(h)=c(jh)$ must be a Garden of Eden for $\mathcal{A}_{H}$. By the discussion above, $\mathcal{A}_{H}$ must have an orphan pattern, which is also an orphan pattern for $\mathcal{A}$. $\Box$

Title Garden of Eden GardenOfEden 2013-03-22 19:22:01 2013-03-22 19:22:01 Ziosilvio (18733) Ziosilvio (18733) 6 Ziosilvio (18733) Definition msc 37B15 msc 68Q80 orphan pattern (cellular automaton) orphan pattern principle