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

Undecidable Properties on the Dynamics of Reversible One-Dimensional Cellular Automata

Jarkko Kari, Undecidable Properties on the Dynamics of Reversible One-Dimensional Cellular Automata. In: Bruno Durand (Ed.), First Symposium on Cellular Automata "Journees Automates Cellulaires" (JAC 2008), Uzes, France, April 21-25, 2008. Proceedings, 3-14, MCCME Publishing House, Moscow, 2008.

Abstract:

Many properties of the dynamics of one-dimensional cellular automata
are known to be undecidable. However, the undecidability proofs often rely on the undecidability of the nilpotency problem, and hence cannot be applied in the case the automaton is reversible. In this talk we review some recent approaches to prove dynamical properties of reversible 1D CA undecidable. Properties considered include equicontinuity (=periodicity), sensitivity, variants of mortality, one-sided expansivity and regularity. All these properties are undecidable, according to recent proofs obtained in collaboration with N.Ollinger or V.Lukkarila.

BibTeX entry:

@INPROCEEDINGS{inpKari_Jarkko08b,
  title = {Undecidable Properties on the Dynamics of Reversible One-Dimensional Cellular Automata},
  booktitle = {First Symposium on Cellular Automata "Journees Automates Cellulaires" (JAC 2008), Uzes, France, April 21-25, 2008. Proceedings},
  author = {Kari, Jarkko},
  editor = {Durand, Bruno},
  publisher = {MCCME Publishing House, Moscow},
  pages = {3-14},
  year = {2008},
}

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

Edit publication