Surjective cellular automata far from the Garden of Eden

被引：0

作者：

Capobianco, Silvio ^{[1
]}

Guillon, Pierre ^{[2
,3
,4
]}

Kari, Jarkko ^{[4
]}

机构：

[1] Tallinn Univ Technol, Inst Cybernet, EE-19086 Tallinn, Estonia

[2] CNRS, Marseille, France

[3] IML, Marseille, France

[4] Univ Turku, Dept Math, SF-20500 Turku, Finland

来源：

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | 2013年 / 15卷 / 03期

基金：

芬兰科学院;

关键词：

cellular automata; amenability; group theory; topological dynamics; symbolic dynamics; algorithmic randomness;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：41 / 60

页数：20