A uniquely ergodic cellular automaton

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Mar 2015Embargo end date: 01 Jan 2013 English Publisher:Elsevier BVJournal:Journal of Computer and System Sciences, volume 81, pages 415-442 (issn: 0022-0000,

Copyright policy )Funded by:AKA | Cellular automata and dis...

Authors: Törmä Ilkka Aleksi;

doi: 10.1016/j.jcss.2014.10.001 , 10.48550/arxiv.1310.0670

arXiv: 1310.0670

A uniquely ergodic cellular automaton

- Summary
- Subjects
- Metrics

Abstract

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

Related Organizations

University of Turku
Finland
Turku Centre for Computer Science
Finland

Keywords

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

Impact byBIP!

	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