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

A Uniquely Ergodic cellular Automaton

Ilkka Törmä, A Uniquely Ergodic cellular Automaton. Journal of Computer and System Sciences 81(2), 415–442, 2015.

http://dx.doi.org/10.1016/j.jcss.2014.10.001

Abstract:

We construct a one-dimensional uniquely ergodic cellular automaton which is not nilpotent. This automaton can perform asymptotically infinitely sparse computation, which nevertheless never disappears completely. The construction builds on the self-simulating automaton of Gács. We also prove related results of dynamical and computational nature, including the undecidability of unique ergodicity, and the undecidability of nilpotency in uniquely ergodic cellular automata.

BibTeX entry:

@ARTICLE{jTorma_Ilkka15a,
  title = {A Uniquely Ergodic cellular Automaton},
  author = {Törmä, Ilkka},
  journal = {Journal of Computer and System Sciences},
  volume = {81},
  number = {2},
  publisher = {Elsevier},
  pages = {415–442},
  year = {2015},
  keywords = {cellular automata, nilpotency, dynamical system, ergodic theory, unique ergodicity},
  ISSN = {0022-0000},
}

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

Publication Forum rating of this publication: level 3

Edit publication