Glider Implies Li-Yorke Chaos for One-dimensional Cellular Automata
Weifeng Jin, Fangyue Chen and Guanrong Chen
By exploiting the mathematical definition of glider for one-dimensional cellular automata (CA), an analytical characterization of its symbolic dynamics is achieved. By means of the releasing transformation, a one-dimensional CA rule with gliders is rigorously proved to present rich and complicated dynamical behaviors. Based on this result, its underlying chaos is characterized in subtle detail, demonstrating that glider implies chaos in the sense of Li-Yorke. This conclusion holds for all general one-dimensional CA, which is an extended discovery in both CA and chaos theory. Then, some quantitative explanations of the intrinsic complexity of the universal rule 110 are offered via the constructive procedures described in this paper. This particularly uncovers that rule 110 is filled with chaotic subsystems “almost everywhere”. Additionally, a total of 30 topologically distinct Bernoulli-shift rules are shown to be chaotic in the sense of Li-Yorke.
Keywords: Cellular automata; symbolic dynamics; glider; chaos; releasing transformation.