A uniquely ergodic cellular automaton

作者：Torma Ilkka^*

来源：Journal of Computer and System Sciences, 2015, 81(2): 415-442.

DOI：10.1016/j.jcss.2014.10.001

• Cellular automata
• Nilpotency
• Dynamical system
• Ergodic theory
• Unique ergodicity

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 Gacs. 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.

• 出版日期2015-3