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

单词	GardenOfEden
释义	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 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 $\\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$
随便看	PrimeRing prime ring PrimeSignature prime signature PrimeSpectrum prime spectrum PrimeSubfield prime subfield PrimeTheoremOfAConvergentSequenceA prime theorem of a convergent sequence, a PrimeTriplesConjecture prime triples conjecture Primitive primitive PrimitiveElementOfBiquadraticField primitive element of biquadratic field PrimitiveElementTheorem primitive element theorem PrimitiveIdeal primitive ideal PrimitiveMatrix primitive matrix PrimitivePermutationGroup primitive permutation group PrimitiveRecursiveEncoding