This website presents information about IoC as of 31 December 2016 and is no longer updated.
Normality, randomness, and the Garden of Eden
Tuesday, 15 May 2013, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B 101
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 arbitrary 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.