zbMATH — the first resource for mathematics

Reliable cellular automata with self-organization. (English) Zbl 0973.68158
Summary: 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 I 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 paper constructs an asynchronous one-dimensional fault-tolerant cellular automaton, with the further feature of “self-organization”. The latter means that unless a large amount of input information must be given, the initial configuration can be chosen homogeneous.

68Q80 Cellular automata (computational aspects)
82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
37B15 Dynamical aspects of cellular automata
82C26 Dynamic and nonequilibrium phase transitions (general) in statistical mechanics
Full Text: DOI arXiv