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 rule N†. 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.
