User Tools

Site Tools

See veebisait esitab teavet KübIst 31. detsembri 2016 seisuga ja seda enam ei uuendata.
This website presents information about IoC as of 31 December 2016 and is no longer updated.

CS Theory Seminars

Normality, randomness, and the Garden of Eden

Silvio Capobianco IoC

Tuesday, 15 May 2013, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B 101


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.

en/teated/2013/capobianco_1.txt · Last modified: 2013/10/14 18:41 by

© Institute of Cybernetics at TUT, Akadeemia tee 21, 12618 Tallinn, Estonia Phone: +372 620 4150 Fax: + 372 620 4151