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

On undecidability of sensitivity of reversible cellular automata

Ville Lukkarila, On undecidability of sensitivity of reversible cellular automata. In: Ramon Alonso-Sanz Anna Lawniczak Genaro Juarez Martinez Kenichi Morita Thomas Worsch Andrew Adamatzky (Ed.), AUTOMATA-2008 Theory and Applications of Cellular Automata, 2008.

Abstract:

It has been shown earlier by Durand, Formenti and Varouchas that equicontinuity and sensitivity are undecidable properties for one-
dimensional cellular automata. It has been shown by Kari and Ollinger that equicontinuity is undecidable for reversible cellular automata also. In this paper it is shown that sensitivity is undecidable for reversible cellular automata.

BibTeX entry:

@INPROCEEDINGS{inpLukkarila08a,
  title = {On undecidability of sensitivity of reversible cellular automata},
  booktitle = {AUTOMATA-2008 Theory and Applications of Cellular Automata},
  author = {Lukkarila, Ville},
  editor = {Andrew Adamatzky, Ramon Alonso-Sanz Anna Lawniczak Genaro Juarez Martinez Kenichi Morita Thomas Worsch},
  year = {2008},
}

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

Edit publication