A Uniquely Ergodic Cellular Automaton
: Ilkka Törmä
Publisher: Elsevier
: 2015
: Journal of Computer and System Sciences
: JCSS
: 81
: 2
: 415
: 442
: 28
: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2014.10.001
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.