## Normality, randomness, and the Garden of Eden

Institute of Cybernetics

Tuesday, 15 October 2013, 14:00 (note the unusual weekday)

Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

**Abstract**: Moore and Myhill's celebrated Garden-of-Eden
theorem states that surjective cellular automata (CA) on a
*d*-dimensional grid are precisely those that satisfy a property
called pre-injectivity, which can be informally described as the
inability of correcting finitely many errors in finite time.

The Garden-of-Eden theorem spawned a rich field of research. On the
one hand, more properties, such as preservation of the product
measure, were found that are equivalent to surjectivity for CA in
arbitrary dimension. On the other hand, however, it became evident
that the Garden-of-Eden theorem does not hold for CA on the free group
on two generators. The fundamental 2010 result by Bartholdi identifies
the groups where surjective CA are pre-injective and preserve the
product measure as the amenable groups, a class introduced by von
Neumann to explain the Banach-Tarski paradox.

This talk covers the work done by the speaker with Pierre Guillon (CNRS)
and Jarkko Kari (University
of Turku) based on a modification by Guillon of Bartholdi's
counterexample. By introducing a definition of normality for
configurations over arbitraryx groups, we quantify the amount of
failure for the preservation of the product measure for CA on
non-amenable groups. For the case of computable groups, where
Martin-Löf randomness of configurations can be defined analogously to
infinite words, we show that the characterization by Calude et al. of
surjective CA in dimension *d* as those that send random
configurations into random configurations, holds in fact precisely for
CA on amenable groups.

Tarmo Uustalu

Last update 17.11.2013