# Garden of Eden

A *Garden of Eden* (briefly, GoE)
for a cellular automaton^{}
$\mathcal{A}=\u27e8Q,\mathcal{N},f\u27e9$
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}=\u27e8Q,\mathcal{N},f\u27e9$
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\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}_{\mathcal{A}}({c}_{n})|}_{{E}_{n}}={p}_{n}={c|}_{{E}_{n}}.$
It is easy to see that
${lim}_{k\to \mathrm{\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\ge 0}$
and a configuration $e:G\to Q$ satisfying
${lim}_{k\to \mathrm{\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}$.
$\mathrm{\square}$

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 |