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

Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata

Jarkko Kari, Ville Lukkarila, Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata. In: D Harel, J. N. Kok, Arto Salomaa, Erik Winfree (Eds.), Algorithmic Bioprocesses, 639–660, Springer, 2009.

Abstract:

Using the fact that the tiling problem of Wang tiles is undecidable even if the given tile set is
deterministic by two opposite corners, it is shown that the question whether there exists a
trajectory which belongs to the given open and closed set is undecidable for one-dimensional
reversible cellular automata. This result holds even if the cellular automaton is mixing.
Furthermore, it is shown that left expansivity of a reversible cellular automaton is an
undecidable property. Also, the tile set construction gives yet another proof for the
universality of one-dimensional reversible cellular automata.

BibTeX entry:

@INBOOK{cKaLu09a,
  title = {Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata},
  booktitle = {Algorithmic Bioprocesses},
  author = {Kari, Jarkko and Lukkarila, Ville},
  editor = {Harel, D and Kok, J. N. and Salomaa, Arto and Winfree, Erik},
  publisher = {Springer},
  pages = {639–660},
  year = {2009},
}

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

Publication Forum rating of this publication: level 2

Edit publication