3
$\begingroup$

Let $L$ be an elementary cellular automaton. Then $L$ acts on $\{0,1\}^{\mathbb{Z}}$. We say that a configuration $w\in\{0,1\}^{\mathbb{Z}}$ is periodic if $L^{(n)}(w)=w$ for some $n\in\mathbb{N}$.

Question: Is there a 'nice' description of all periodic configurations?

$\endgroup$
3
  • $\begingroup$ What kind of answer do you expect? A list of "nice" descriptions one for each elementary cellular automaton? $\endgroup$
    – Algernon
    Mar 6, 2015 at 22:53
  • $\begingroup$ For example, take the elementary cellular automaton rule 90. Is the set of periodic configurations a sofic subshift? If no, is there a way to describe this set by some type of recognition automata? $\endgroup$ Mar 7, 2015 at 7:00
  • $\begingroup$ My point was that your question is neither general enough nor specific enough to receive any meaningful answer. You ask whether there is a nice description of something in any of 256 different objects. If you had asked a universal description for all cellular automata, then one could have answered "No, there is no nice description". If you had asked the same for a specific automaton (say, rule 90), then one might or might not have been able to provide you with a nice description. Instead, your question in its current form consists of 256 separate questions. $\endgroup$
    – Algernon
    Mar 7, 2015 at 14:03

2 Answers 2

2
$\begingroup$

In Periodic Points for Onto Cellular Automata, Boyle and Kitchens have results which give some sufficient conditions for the periodic points of a CA to be dense in a shift. One of these sufficient conditions is for the alphabet $A$ to be a finite group and the CA to be a group homomorphism from the full shift to itself (viewed as the direct product $A^{\mathbb{Z}}$); this is Proposition 3.2.

The specific case of Rule 90 meets ]this criteria, so its periodic points are dense in the full shift $(C_2)^{\mathbb{Z}}$. However, not all points are periodic under this rule; see the configuration which is ON only at a single cell. So the set of Rule 90-periodic configurations is not topologically closed and can't be a sofic shift.

There are other criteria given in the paper, and I think it would be interesting to see which ones apply to the one-dimensional Wolfram rules.

$\endgroup$
2
$\begingroup$

Let me refer to your property as (temporal) periodicity, and to shift-periodicity as spatial periodicity.

Rule 110

I would guess that for rule 110 there is no simple description of the temporally periodic points, in a precise sense.

First, there is no description of the periodic points for cellular automata in general: There exists a cellular automaton such that given a finite word, it is undecidable (more precisely $\Sigma^0_1$-complete) whether it appears in a temporally periodic configuration. Hardness can be proved by simulating a universal Turing machine. The set of words appearing in a temporally periodic configuration is recursively enumerable, since every word that appears in a temporally periodic point appears in a point that is temporally periodic and spatially eventually periodic in both directions. This can be shown by a pigeonhole argument.

Rule 110 is well-known to be Turing-complete, so it would not be surprising if it has this property. Something quite similar is stated by Matthew Cook in his paper about its universality, let me quote his paper:

As discussed in Section 2.3, given a fixed repeating pattern to the left and right, it is undecidable whether a given finite initial condition will lead to periodicity in Rule 110’s behavior.

However, I think that here, "periodicity" refers to "eventual periodicity". I do not know the details of rule 110 well-enough to know to say how hard the set of words that appear in periodic points (or the set of periodic points itself) is.

Rule 90

In the case of rule 90, there is a simple algebraic description of temporally periodic points.

First, rule 90 is positively expansive, so it can have only finitely many temporally periodic points for each period. (Proof: The $p$-periodic points form a subshift of finite type. An infinite subshift has two configurations that are left-asymptotic, which contradicts positive expansivity.) This obviously implies that every temporally periodic point is spatially periodic. So we only have to figure out which spatially periodic points are temporally periodic.

The rule is also linear, in the sense that if we look at $\ell$-periodic configurations as vectors over the two-element field $F_2$, then rule $90$ is a linear map. Call this vector space of periodic points $V_{\ell}$, identify them with binary words of length $\ell$, and let $M$ be the (circulant) matrix by which rule $90$ acts on it.

Obviously if a point $v \in V_{\ell}$ is temporally periodic for $M$, then $v$ is in the eventual image of $M$. The converse holds, since a matrix is invertible on its eventual image, and since bijections on a finite set are periodic.

So we only have to figure out the eventual image of $M$. This is precisely the set of vectors that are in the image of $M^{2^n}$ for all $n$, since the numbers $2^n$ are a cofinal set in $\mathbb{N}$. Let $v_1$ be the vector $10^{\ell-1}$. By linearity, it is enough to describe the vector space generated by $M^{2^n}(v_1)$ for arbitrarily large $n$. Let $\ell = 2^h \cdot m$ where $m$ is odd.

Now, let $j$ be the order of $2$ in $\mathbb{Z}_m^*$ and observe that $M^{2^{h + nj}}(v_1) = 1 0^{2^h - 1} 1 0^{\ell - 2^h - 1}$ for all $h$, and that in any $M^{2^{h + n}}(v_1)$ there are exactly $2$ ones, and the second is in a position which is divisible by $2^h$. Such vectors generate precisely the vector space $E_{m, 2^h} \leq V_{\ell}$ consisting of those words where in each arithmetic progression with step $2^h$ you have an even number of $1$s. We have obtained the following (words indexed from $0$, $0 \in \mathbb{N}$, $0$ is even):

Pick $h \in \mathbb{N}$, and pick any $2^h$ words $w^0, w^1, ..., w^{2^h-1}$ each of the same odd length $m$, and each containing an even number of $1$s. Intersperse those words to obtain the word $w = w^0_0 w^1_0 ... w^{2^h-1}_0 w^0_1 w^1_1 ... w^{2^h-1}_{m-1}$. Then $...wwww...$ is temporally periodic for rule $90$. Every temporally periodic point is obtained in this way.

For odd $m$ this condition is the same as having an even number of $1$s. E.g. for period $11$, $10000100010$ is not periodic because it has $3$ ones. And indeed $f(10000100010) = f^{342}(10000100010)$, but $10000100010$ does not occur in this cycle. On the other hand $01010100010$ has an even number of ones and indeed $f^{341}(01010100010) = 01010100010$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.