期刊
JOURNAL OF STATISTICAL PHYSICS
卷 103, 期 1-2, 页码 45-267出版社
SPRINGER
DOI: 10.1023/A:1004823720305
关键词
probabilistic cellular automata; interacting particle systems; renormalization; ergodicity; reliability; fault-tolerance; error-correction; simulation; hierarchy; self-organization
In a probabilistic cellular automaton in which all local transitions have positive probability. the problem of keeping a bit of information indefinitely is nontrivial, even in an infinite automaton. Still, there is a solution in 2 dimensions, and this solution can be used to construct a simple 3-dimensional discrete-time universal fault-tolerant cellular automaton. This technique does not help much to solve the following problems: remembering a bit of information in 1 dimension: computing in dimensions lower than 3; computing in any dimension with non-synchronized transitions. Our more complex technique organizes the cells in blocks that perform a reliable simulation of a second (generalized) cellular automaton. The cells of the latter automaton are also organized in blocks; simulating even more reliably a third automaton, etc. Since all this (a possibly infinite hierarchy) is organized in software, it must be under repair all the time from damage caused by errors. A large part of the problem is essentially self-stabilization recovering from a mess of arbitrary size and content. The present payer constructs an asynchronous one-dimensional fault-tolerant cellular automaton, with the further feature of self-organization. The latter means that unless a large amount or input information must be given, the initial configuration can be chosen homogeneous.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据