Sensitivity and Topological Mixing are Undecidable for Reversible One-dimensional Cellular Automata
Ville Lukkarila
It is shown by a reduction from the reversible Turing machine halting problem that sensitivity is undecidable even for reversible one-dimensional cellular automata. With a few additional constructions, the undecidability of topological mixing and the undecidability of topological transitivity follow. Furthermore, sets of topologically mixing cellular automata and non-sensitive cellular automata are recursively inseparable. It follows that Devaney’s chaos and Knudsen’s chaos are undecidable dynamical properties.
Keywords: Cellular automata, Chaos, Sensitivity to initial conditions, Topological mixing, Topological transitivity, Undecidability