Dynamical behavior

Our objective in studying dynamical behavior of reversible one dimensional cellular automata is understanding the conditions that an initial configuration must hold to evolves in a particular behavior. In this way, in one dimensional cellular automata we define an orbit in the following way:

Definition 8   In one dimensional cellular automata, for $i \in {\mathbb{N}}$ and configurations ${{c}_{i}} \in {{C}_{}}$, an orbit ${\mathit{e}_{}}={\left\{ {{c}_{0}},{{c}_{1}},\ldots,{{c}_{i}},\ldots \right\} }$ is the sequence of configurations such that configuration ${{c}_{i+1}}$ is the evolution of the configuration ${{c}_{i}}$

Given an orbit ${\mathit{e}_{}}$, its behavior is characterized by the cylinder sets that it reaches and in what way it passes these cylinder sets. For covering the configuration space ${({{C}_{}},{\mathfrak{C}_{}})}$, we only use the set ${K^{3}}$ of finite sequences with $3$ cells. We do this because for $({k^{}},1/2)$ reversible one dimensional cellular automata, sequences of $3$ cells are that we need to form the block permutations, that is, sequences of length $6{r_{}}$. Block permutations define the transition from one sequence of $3$ cells to another sequence with the same length, so we can see that as the transition from one cylinder set to another cylinder set. There exists a shift among these sequences of length $3{r_{}}$, or of length $3/2$ cells with neighborhood size $2$. To obtain a shift of equal length that the sequences, we define an evolution rule ${\varphi}^\prime ={{\varphi} \circ {\varphi}}$, that is, an evolution rule that is the composition of the original evolution rule. This process is not necessary but is useful because allows us to work with centered cylinder sets.

To have a simpler notation in this section, we shall use the symbol ${\varphi}$ to reference the composition of the original evolution rule, and the symbol ${\varphi^{-1}}$ to reference the composition of the inverse evolution rule. These invertible evolution rules induce global mappings ${\Phi}$ and ${\Phi^{-1}}$ that map one sequence of $3$ cells to another sequence with the same length and a shift among them of $3$ cells. In other words, for an orbit ${\mathit{e}_{}}$ defined with this evolution rule, we have a mapping from a centered cylinder set ${\mathcal{C}_{[{{c}_{i{[-1,1]}}}]}}$ to a centered cylinder set ${\mathcal{C}_{[{{c}_{i+1{[-1,1]}}}]}}$ as we can see in Figure 9.

Figure: Passing from the centered cylinder set ${\mathcal{C}_{[{{c}_{i{[-1,1]}}}]}}$ to the centered cylinder set ${\mathcal{C}_{[{{c}_{i+1{[-1,1]}}}]}}$ using the composition of evolution rules in a $({k^{}},1/2)$ reversible one dimensional cellular automaton

Based on block permutations, we present simple matrix methods for detecting the existence of different kind of orbits.