Chapter 2. Period-3, Period-6, and Permutive Rules

This 12th part of our Nonlinear Dynamics Perspective of Cellular Automata concludes a series of three articles devoted to CA local rules having robust periodic ω-limit orbits. Here, we consider only the two rules, 131 and 133, constituting the third of the six groups in which we classified the 1D binary Cellular Automata. Among the numerous theoretical results contained in this article, we emphasize the complete characterization of the ω-limit orbits, both robust and nonrobust, of these two rules and the proof that period-3 and period-6 ω-limit orbits are dense for 131 and 133, respectively. Furthermore, we will also introduce the fundamental concepts of perfect period-T orbit sets and riddled basins, and see how they emerge in rule 131.

As stated in the title, we also focus on permutive rules, which have been introduced in a previous installment of our series but never thoroughly studied. Indeed, we will review some of the well-known properties of such rules, like the surjectivity, examining their implications for finite and bi-infinite Cellular Automata.

Finally, we propose a new list of the 88 globally-independent local rules, which is slightly different from the one we have used so far but has the great advantage of being selected via a rigorous methodology and not an arbitrary choice. For the sake of completeness, we display in the appendix the basin tree diagrams and the portraits of the ω-limit orbits of the rules from this refined table which have not yet been reported in our previous articles.