• 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. TUCS Technical Reports 927, Turku Centre for Computer Science, 2009.

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 nonsensitive cellular automata are recursively inseparable. It follows that Devaney's chaos and Knudsen's chaos are undecidable dynamical properties. [This paper has been submitted to Journal of Cellular Automata in September 2008.]

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tLukkarila09a,
  title = {Sensitivity and Topological Mixing are Undecidable for Reversible One-Dimensional Cellular Automata},
  author = {Lukkarila, Ville},
  number = {927},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2009},
  keywords = {cellular automata, chaos, sensitivity, topological transitivity, topological mixing},
  ISBN = {978-952-12-2238-2},
}

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

Edit publication