Silvio Capobianco ; Pierre Guillon ; Jarkko Kari - Surjective cellular automata far from the Garden of Eden

dmtcs:618 - Discrete Mathematics & Theoretical Computer Science, October 18, 2013, Vol. 15 no. 3 - https://doi.org/10.46298/dmtcs.618
Surjective cellular automata far from the Garden of EdenArticle

Authors: Silvio Capobianco ORCID1; Pierre Guillon ORCID2,3; Jarkko Kari ORCID2

  • 1 Institute of Cybernetics [Tallinn]
  • 2 Department of Mathematics
  • 3 Institut de mathématiques de Luminy

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.


Volume: Vol. 15 no. 3
Section: Automata, Logic and Semantics
Published on: October 18, 2013
Accepted on: June 9, 2015
Submitted on: December 7, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Cellular automata and discrete dynamical systems; Funder: Research Council of Finland; Code: 131558

1 Document citing this article

Consultation statistics

This page has been seen 508 times.
This article's PDF has been downloaded 506 times.