A special kind of pseudo-garden eden states in cellular automata

Question

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

Rule 73

Rule 110

Rule 18

Rule 45

Answer 1

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