0
$\begingroup$

I'm currently investigating Wolfram's elementary cellular automata on finite grids with periodic boundary conditions, i.e. on $\mathbb{Z}/k$ for different $k$.

It is clear that for each rule $R$ and each state space $\Sigma_k = \{2^k\}$ there are three kinds of states:

  • garden eden states $\alpha$, i.e. states without predecessor $\beta$ with $\Phi_R(\beta) = \alpha$

  • periodic states $\omega$, i.e. states lying on a limit cycle

  • transient states $\tau$, i.e. states lying on shortest trajectories going from some $\alpha$ to some $\omega$.

It turns out that there are limit cycles of which some but not all periodic states $\omega$ are "targets" of some garden eden state: their unique predecessor lies on the same limit cycle. Let's call these states $\gamma$ pseudo-garden eden states (without further reason).

I wonder if $\gamma$ states were found worth to be investigated. We know that garden eden states may be characterized by local patterns not reachable/producable by any predecessor $\beta$. Might there be a similar characterization of pseudo-garden eden states?

For some rules $R$ and numbers $k$ pseudo-garden eden states appear periodically, for others they come irregularly. In the following examples the non-$\gamma$ states – i.e. states where a transient meets the limit cycle – are marked with their index.

Rule 26

enter image description here enter image description here enter image description here

Rule 73

enter image description here enter image description here enter image description here

Rule 110

enter image description here enter image description here enter image description here

Rule 18

enter image description here enter image description here enter image description here

Rule 45

enter image description here enter image description here

$\endgroup$
3
  • $\begingroup$ Usually we say "orphan", not "kink", for patterns that do not appear in the image. As far as I understand your pseudo gardens of eden form a regular language for any 1d CA, in the sense that a single FSA describes them simultaneously for all cycle sizes $k$. Not sure what your exact question is though. $\endgroup$
    – Ville Salo
    Commented Oct 5, 2022 at 18:46
  • $\begingroup$ @VilleSalo: Can you please give me a reference to learn how PGE states form a regular language? $\endgroup$ Commented Oct 5, 2022 at 18:54
  • $\begingroup$ @VilleSalo: The question could be: which specific regular language (expression?) do they form? How do I find/construct it? $\endgroup$ Commented Oct 5, 2022 at 20:52

1 Answer 1

2
$\begingroup$

Your definition is not very clear to me, but I'll try my best. Let $O \subset \{0, 1\}^*$ be the set of words (considered cyclic for the purpose of CA application) which lie on a limit cycle. Let $A \subset \{0, 1\}^*$ be the gardens of eden, and $T \subset \{0, 1\}^*$ the transients (i.e. complement of $O \cup A$).

Let $U \subset \{0, 1\}^*$ be the set of configurations that have a unique preimage (let's say we don't include $A$, doesn't really matter). As far as I understand, your $\gamma$s are the set $U \cap O$.

I don't know what you can say about $U \cap O$, you'd have to look on a rule-by-rule basis, as the ECA have nothing in common. I'll mention my tangentially related answer here, which studies numbers of preimages of $f^n(...00100...)$ in rule 110, The graph of Rule 110 and vertices degree

What, I can say is the following:

  • $A$ is a regular language. In fact, the de Bruijn representation of the rule gives a finite-state automaton for the language of the image subshift of the CA $f$ (i.e. for the finite words appearing in $f(\{0,1\}^{\mathbb{Z}}) \subset \{0,1\}^{\mathbb{Z}}$). You can make it check for a periodic preimage by making it remember the beginning of the word and checking consistency at the end, it's a simple exercise.
  • $O$ is not always regular, for example it's not regular for rule 90, see Periodic configurations for elementary cellular automata . You would have to look at this on a rule-by-rule basis.
  • $T$ is just the complement of the disjoint union $A \dot\cup O$, so it's regular iff $O$ is.
  • $U$ is regular. The proof is similar as for $A$. The general statement is that anything you can write with a first-order formula gives you a regular language. I explain with $U$. The set $U$ consists of $x$ satisfying $$\exists y: f(y) = x \wedge \forall z: (f(z) = x \implies z = y)$$ Pull out quantifiers to get $\exists y: \forall z: f(y) = x \wedge (f(z) = x \implies z = y)$. Observe that like the automaton for $A$ we can write an automaton that accepts triples $(x, y, z) \in (\{0,1\}^3)^*$, thought of as periodic words, such that the formula above holds, i.e. $f(y) = x \wedge (f(z) = x \implies z = y)$. Now, we do quantifier elimination. To eliminate $\exists$ on one layer is just symbol projection, and NFA are clearly closed under that. To eliminate $\forall$, use duality (complement with subset construction, eliminate $\exists$, complement back).
$\endgroup$
1
  • $\begingroup$ Great! Thanks a lot. $\endgroup$ Commented Oct 6, 2022 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.