A uniquely ergodic cellular automaton
Copyright policy )A uniquely ergodic cellular automaton
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.
47 pages, 8 figures. Submitted to Journal of Computer and System Sciences
- University of Turku Finland
- Turku Centre for Computer Science Finland
Cellular automata (computational aspects), ta113, FOS: Computer and information sciences, ergodic theory, Formal Languages and Automata Theory (cs.FL), cellular automata, ta111, unique ergodicity, Computer Science - Formal Languages and Automata Theory, Dynamical Systems (math.DS), dynamical system, Dynamical aspects of cellular automata, FOS: Mathematics, Mathematics - Dynamical Systems, nilpotency
Cellular automata (computational aspects), ta113, FOS: Computer and information sciences, ergodic theory, Formal Languages and Automata Theory (cs.FL), cellular automata, ta111, unique ergodicity, Computer Science - Formal Languages and Automata Theory, Dynamical Systems (math.DS), dynamical system, Dynamical aspects of cellular automata, FOS: Mathematics, Mathematics - Dynamical Systems, nilpotency
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!