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