Skip to Main content Skip to Navigation

Surjective cellular automata far from the Garden of Eden

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, March 26, 2014 - 3:16:24 PM
Last modification on : Friday, May 10, 2019 - 1:44:06 PM
Document(s) archivé(s) le : Thursday, June 26, 2014 - 11:31:55 AM


Files produced by the author(s)


  • HAL Id : hal-00966380, version 1



Silvio Capobianco, Pierre Guillon, Jarkko Kari. Surjective cellular automata far from the Garden of Eden. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 3 (3), pp.41--60. ⟨hal-00966380⟩



Record views


Files downloads