A1 Refereed original research article in a scientific journal
A Uniquely Ergodic Cellular Automaton
Authors: Ilkka Törmä
Publisher: Elsevier
Publication year: 2015
Journal: Journal of Computer and System Sciences
Journal acronym: JCSS
Volume: 81
Issue: 2
First page : 415
Last page: 442
Number of pages: 28
ISSN: 0022-0000
DOI: https://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.
Downloadable publication This is an electronic reprint of the original article. |