Detecting transitive behavior in $({k^{}},1/2)$ reversible one dimensional cellular automata

Using the process presented in section 5.4, we can define a transition relation among sequences ${w_{}}$ in the set ${K^{3}}$. In this way, we have a surjective mapping from the set ${K^{3}}$ to itself, since every sequence has at least one ancestor. In this transition relation, the indices are sequences ${w_{}}$ of $3$ cells and the elements show the mapping from one sequence ${w_{i}}$ to a set of sequences ${w_{m}}$ as is presented in Table 2.

Table 2: Transitive relation among sequences of the set ${K^{3}}$ defined by block permutations

sequences
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
${w_{i}}$	$\vdots$	1	$\cdots$	1	$\vdots$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
	$\cdots$	${w_{m}}$	$\cdots$	${w_{m}}$	$\cdots$	sequences

As in the connectivity relation defined in Table 1, we can do the transitive closure of the transition relation. Depending of the number of classes that we get with this process, we will detect different kinds of transitive behavior among centered cylinder sets defined by sequences in the set ${K^{3}}$.

Lemma 1   If the transitive closure of the transition relation in Table 2 forms one unique class, then the $({k^{}},1/2)$ reversible one dimensional cellular automaton is topologically ergodic

Proof. For every sequence ${w_{}}$ in the set ${K^{3}}$, if the transitive closure forms an unique class, then it shows that there exists an orbit ${\mathit{e}_{}}$ from the centered cilinder set ${\mathcal{C}_{[{w_{}}]}}$ to all the others centered cylinder sets, and therefore the centered cylinder set ${\mathcal{C}_{[{w_{}}]}}$ is topologically ergodic. Since we have only one unique class, then all sequences ${w_{}}$ in the set ${K^{3}}$ carry out with the previous statement, and the centered cylinder sets defined by these sequences are topologically ergodic. $\qedsymbol$

In the configuration space ${({{C}_{}},{\mathfrak{C}_{}})}$, if a $({k^{}},1/2)$ reversible one dimensional cellular automaton defines a topologically ergodic dynamical system then for every ${w_{}}\in {K^{3}}$, there exists a configuration ${{c}_{}}$ which belongs to the centered cylinder set ${\mathcal{C}_{[{w_{}}]}}$ and it has an orbit through all the other centered cylinder sets defined by the sequences in the set ${K^{3}}$. Thus, a consequence of Lemma 1 is the following:

Corollary 2   A topologically ergodic $({k^{}},1/2)$ reversible one dimensional cellular automaton has topologically transitive configurations.

Finally, the transition relation and its transitive closure give us important information about the mixing behavior of $({k^{}},1/2)$ reversible one dimensional cellular automata. In the transition relation, the $1's$ in the principal diagonal indicate centered cylinder sets which can return to the same centered cylinder set in one step. In other words, the principal diagonal shows centered cylinder sets that can be fixed.

Using the principal diagonal and the transitive closure of the transition relation, we have the following result:

Theorem 2   If a $({k^{}},1/2)$ reversible one dimensional cellular automaton is topologycally ergodic and its transition relation has a non-zero principal diagonal, then the automaton is topologically mixing

Proof. Because the principal diagonal is non-zero, there exists at least one centered cylinder set that can be fixed. Since the automaton is ergodic, there exists an orbit ${\mathit{e}_{}}$ from any centered cylinder set to a centered cylinder set that can be fixed. Thus, this orbit in this centered cylinder set can remain there $n$ steps for $n \in {\mathbb{Z}^+}$, and then goes out to another centered cylinder set. So, beginning in every centered cylinder set, we can reach any other centered cylinder set in the number of steps that we want, therefore every centered cylinder set is topologically mixing. $\qedsymbol$

In this way, we have defined simple matrix methods that using the properties of block permutations and transitive closures detect periodical and transitive behavior. Of course, a big problem is that these methods only detect the existence of these orbits but they doesn't give an explicit example of them.