A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

A Uniquely Ergodic Cellular Automaton




TekijätIlkka Törmä

KustantajaElsevier

Julkaisuvuosi2015

JournalJournal of Computer and System Sciences

Lehden akronyymiJCSS

Vuosikerta81

Numero2

Aloitussivu415

Lopetussivu442

Sivujen määrä28

ISSN0022-0000

DOIhttps://doi.org/10.1016/j.jcss.2014.10.001


Tiivistelmä

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.



Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 17:47