2013/10/02 by Ilkka Törmä, Törmä, Ilkka
Computer Science · Mathematics · #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.FL #math.DS
paper · pdf · doi:10.48550/arxiv.1310.0670
47 pages, 8 figures. Submitted to Journal of Computer and System Sciences
arxiv created 2014/08/28 · arxiv updated 2014/08/29
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.