• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Sensitivity and Topological Mixing are Undecidable for Reversible One-dimensional Cellular Automata

Ville Lukkarila, Sensitivity and Topological Mixing are Undecidable for Reversible One-dimensional Cellular Automata. Journal of Cellular Automata 5(3), 241–272, 2010.

Abstract:

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.

BibTeX entry:

@ARTICLE{jLukkarila10a,
  title = {Sensitivity and Topological Mixing are Undecidable for Reversible One-dimensional Cellular Automata},
  author = {Lukkarila, Ville},
  journal = {Journal of Cellular Automata},
  volume = {5},
  number = {3},
  pages = {241–272},
  year = {2010},
  keywords = {Cellular automata, Chaos, Sensitivity to initial conditions, Topological mixing, Topological transitivity, Undecidability},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication