A Uniquely Ergodic Cellular Automaton

2013 
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\'acs. 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.
    • Correction
    • Cite
    • Save
    • Machine Reading By IdeaReader
    11
    References
    0
    Citations
    NaN
    KQI
    []