A1 Refereed original research article in a scientific journal
Surjective cellular automata far from the Garden of Eden
Authors: Silvio Capobianco, Pierre Guillon, Jarkko Kari
Publisher: Discrete Mathematics & Theoretical Computer Science
Publication year: 2013
Journal: Discrete Mathematics and Theoretical Computer Science
Journal acronym: DMTCS
Number in series: 3
Volume: 15
Issue: 3
First page : 41
Last page: 60
Number of pages: 20
ISSN: 1462-7264
DOI: https://doi.org/10.46298/dmtcs.618
Web address : https://dx.doi.org/10.46298/dmtcs.618
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/2052752
One of the first and most famous results of cellular automata theory, Moore’s Garden-of-Eden theorem has been proven to hold if and only if the underlying group possesses the measure-theoretic properties suggested by von Neumann to be the obstacle to the Banach-Tarski paradox. We show that several other results from the literature, already known to characterize surjective cellular automata in dimension d, hold precisely when the Garden-of-Eden theorem does. We focus in particular on the balancedness theorem, which has been proven by Bartholdi to fail on amenable groups, and we measure the amount of such failure.
Downloadable publication This is an electronic reprint of the original article. |  |
