A Uniquely Ergodic Cellular Automaton




Ilkka Törmä

PublisherElsevier

2015

Journal of Computer and System Sciences

JCSS

81

2

415

442

28

0022-0000

DOIhttps://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.



Last updated on 2024-26-11 at 17:47