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

Decidability and Undecidability in Cellular Automata

Jarkko Kari, Decidability and Undecidability in Cellular Automata. International Journal of General Systems 41(6), 539–554, 2012.

Abstract:

We survey results on decidability questions concerning cellular automata. Properties discussed include reversibility and surjectivity and their variants, time-symmetry and conservation laws, nilpotency and other properties of the limit set and the trace, properties chaoticity related such as sensitivity to initial conditions and mixing of the space, and dynamics from finite initial configurations. We also discuss briefly the tiling problem and its variants, and consider the influence of the dimension of the space on the decidability status of the questions.

BibTeX entry:

@ARTICLE{jKari_Jarkko12a,
  title = {Decidability and Undecidability in Cellular Automata},
  author = {Kari, Jarkko},
  journal = {International Journal of General Systems},
  volume = {41},
  number = {6},
  pages = {539–554},
  year = {2012},
}

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

Publication Forum rating of this publication: level 1

Edit publication