Periodic behavior of $({k^{}},1/2)$ reversible one dimensional cellular automata

In the paper of Hedlund [Hed69], section 7 is devoted to analyse the dynamical behavior of the shift systems; based on his work we will do an analysis of periodic orbits in $({k^{}},1/2)$ reversible one dimensional cellular automata.

Suppose that a given configuration ${{c}_{}}$ in the configuration set ${{C}_{}}$ is formed by the successive repetition of a finite sequence ${w_{}}$ of $n$ cells. Thus, the states that form this configuration have a period $n$. Now, suppose that we apply an invertible evolution rule ${\varphi}$, since the action of this rule is a block permutation, we can characterize the periodical behavior under the global mapping ${\Phi}$ induced by ${\varphi}$ of a configuration ${{c}_{}}$ formed by a periodical finite sequence ${w_{}}\in {K^{n}}$.

Theorem 1   Given a $({k^{}},1/2)$ reversible one dimensional cellular automaton and a configuration ${{c}_{}}$ formed with the successive repetition of a finite sequence ${w_{}}$ of length $n$, the maximum period of the orbit formed with the configuration ${{c}_{}}$ is ${k^{3n}}$

Proof. The configuration ${{c}_{}}$ is formed with a periodic finite sequence ${w_{}}$ of $n$ cells, take a sequence of ${w_{1}}$ of $3n$ cells in the configuration ${{c}_{}}$. The sequence ${w_{1}}$ has a period of length $3n$ because is the repetition of a periodic sequence ${w_{}}$ of $n$ cells. But ${w_{1}}$ also has $n$ sequence of $3$ cells each one of them, applying the global mapping ${\Phi}$, every sequence of $3$ cells maps to another unique sequence of $3$ cells as is showed by the block permutations. Then the complete sequence ${w_{1}}$ of $3n$ cells maps to an unique sequence ${w_{2}}$ of $3n$ cells too.

Since all the sequences of length $3n$ cells are in the finite set ${K^{3n}}$, and the cardinality of the set ${K^{3n}}$ is ${\mid{K^{3n}}\mid}={k^{3n}}$, then in some moment during the evolution of the automaton we have to repeat the same sequence ${w_{1}}$. Thus, the maximum period of the configuration ${{c}_{}}$ formed with the repetition of a finite sequence ${w_{}}$ of length $n$ is ${k^{3n}}$. $\qedsymbol$

In the general case of $({k^{}},r)$ reversible one dimensional cellular automata, Theorem 1 defines a maximum period of $6{r_{}}n$ steps; where ${r_{}}$ is the neighborhood radius and $n$ is the length of the finite sequence ${w_{}}$ whose repetition forms the configuration ${{c}_{}}$. We have to point out that this maximum period in most cases is a bad quote, because the practical experience shows that this period is much smaller.

Periodic orbits ${\mathit{e}_{}}$ of period $n$ goes from a centered cylinder set to the same cilinder set. Since every sequence ${w_{}}$ of length $3$ cells defines a centered cylinder set, then the family of all centered cilinder sets forms a finite covering of the configuration space ${({{C}_{}},{\mathfrak{C}_{}})}$. Then, a consequence of Theorem 1 and using Definition 6 is the following:

Corollary 1   For every sequence ${w_{}}\in {K^{3}}$, the centered cylinder set ${\mathcal{C}_{[{w_{}}]}}$ is a non-wandering set.

Proof. Take every sequence ${w_{}}$ in ${K^{3}}$, and form a configuration ${{c}_{}}$ with the successive repetition of ${w_{}}$. Then the configuration ${{c}_{}}$ belongs to the centered cylinder set ${\mathcal{C}_{[{w_{}}]}}$ and is periodic with finite period by Theorem 1. Thus, the orbit of ${{c}_{}}$ returns to the same centered cylinder set ${\mathcal{C}_{[{w_{}}]}}$ and therefore is non-wandering $\qedsymbol$

Now we will use block permutations for detecting the periodical behavior of these systems.