Narrow Results

We prove rigorously the four cellular automata local rules 110, 124, 137 and 193 have identical dynamic behaviors capable of universal computations. We exploit Felix Klein's remarkable Vierergruppe to partition the 256 local rules studied empirically by Wolfram into 89 global equivalence classes of which only 50 may exhibit complex dynamics. We define a 24-element rotation group which induces 30 local equivalence classes of nonlinear difference equations whose parameters can be mapped into each other among members of the same class.

This paper proves, via an analytical approach, that 170 (out of 256) Boolean CA rules in a one-dimensional cellular automata (CA) are time-reversible in a generalized sense. The dynamics on each attractor of a time-reversible rule N is exactly mirrored, in both space and time, by its bilateral twin ruleN^†. In particular, all 69 period-1 rules, 17 (out of 25) period-2 rules, and 84 (out of 112) Bernoulli rules are time-reversible.

The remaining 86 CA rules are time-irreversible in the sense that N and N^† mirror their dynamics only in space, but not in time. In this case, each attractor of N defines a unique arrow of time.

A simple "time-reversal test" is given for testing whether an attractor of a CA rule is time-reversible or time-irreversible. For a time-reversible attractor of a CA rule N the past can be uniquely recovered from the future of N^†, and vice versa. This remarkable property provides 170 concrete examples of CA time machines where time travel can be routinely achieved by merely hopping from one attractor to its bilateral twin attractor, and vice versa. Moreover, the time-reversal property of some local rules can be programmed to mimic the matter–antimatter "annihilation" or "pair-production" phenomenon from high-energy physics, as well as to mimic the "contraction" or "expansion" scenarios associated with the Big Bang from cosmology.

Unlike the conventional laws of physics, which are based on a unique universe, most CA rules have multiple universes (i.e. attractors), each blessed with its own laws. Moreover, some CA rules are endowed with both time-reversible attractors and time-irreversible attractors.

Using an analytical approach, the time-τ return map of each Bernoulli στ-shift attractor of all 112 Bernoulli rules are shown to obey an ultra-compact formula in closed form, namely,.

or its inverse map.

These maps completely characterize the time-asymptotic (steady state) behavior of the nonlinear dynamics on the attractors. In-depth analysis of all but 18 global equivalence classes of CA rules have been derived, along with their basins of attraction, which characterize their transient regimes.

Above all, this paper provides a rigorous nonlinear dynamics foundation for a paradigm shift from an empirical-based approach à la Wolfram to an attractor-based analytical theory of cellular automata.

This stage of our journey through the universe of one-dimensional binary Cellular Automata is devoted to period-1 rules, constituting the first of the six groups in which we systematized the 88 globally-independent CA rules.

The first part of this article is mainly dedicated to reviewing the terminology and the empirical results found in the previous papers of our quest. We also introduce the concept of the ω-limit orbit with the purpose of linking our work to the classical theory of nonlinear dynamical systems. Moreover, we present the basin tree diagrams of all period-1 rules — except for rule , which is trivial — along with their Boolean cubes and time-1 characteristic functions.

In the second part, we prove a theorem demonstrating that all rules belonging to group 1 have robust period-1 rules for any finite, and infinite, bit-string length L. This is the first time we give analytical results on the behavior of CA local rules for large values of L and, consequently, for bi-infinite bit strings.

The theoretical treatment is complemented by two remarkable practical results: an explicit formula for generating isomorphic basin trees, and an algorithm for creating new periodic orbits by concatenation. We also provide several examples of both of them, showing how they help to avoid tedious simulations.

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, and , 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 and , respectively. Furthermore, we will also introduce the fundamental concepts of perfect period-T orbitsets and riddled basins, and see how they emerge in rule .

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.

This stage of our journey through the universe of one-dimensional binary Cellular Automata is devoted to period-1 rules, constituting the first of the six groups in which we systematized the 88 globally-independent CA rules.

The first part of this article is mainly dedicated to reviewing the terminology and the empirical results found in the previous papers of our quest. We also introduce the concept of the ω-limit orbit with the purpose of linking our work to the classical theory of nonlinear dynamical systems. Moreover, we present the basin tree diagrams of all period-1 rules — except for rule , which is trivial — along with their Boolean cubes and time-1 characteristic functions.

In the second part, we prove a theorem demonstrating that all rules belonging to group 1 have robust period-1 rules for any finite, and infinite, bit-string length L. This is the first time we give analytical results on the behavior of CA local rules for large values of L and, consequently, for bi-infinite bit strings.

The theoretical treatment is complemented by two remarkable practical results: an explicit formula for generating isomorphic basin trees, and an algorithm for creating new periodic orbits by concatenation. We also provide several examples of both of them, showing how they help to avoid tedious simulations.

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 orbitsets 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.