文章基本信息

标题：Intrinsic Simulations between Stochastic Cellular Automata
本地全文：下载
作者：Pablo Arrighi ; Nicolas Schabanel ; Guillaume Theyssier 等
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2012
卷号：90
页码：208-224
DOI：10.4204/EPTCS.90.17
出版社：Open Publishing Association
摘要：The paper proposes a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in a unifying and composable manner. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. We then provide explicit tools to prove or disprove the existence of such a simulation between two stochastic cellular automata, even though the intrinsic simulation relation is shown to be undecidable in dimension two and higher. The key result behind this is the caracterization of equality of stochastic global maps by the existence of a coupling between the random sources. We then prove that there is a universal non-deterministic cellular automaton, but no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality.