Surjective cellular automata far from the Garden of Eden
Silvio Capobianco, Pierre Guillon, Jarkko Kari
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.
Full Text: PDF PostScript