Reliable Cellular Automata With anization - Peter Gacs.pdf

RELIABLE CELLULAR AUTOMATA WITH ANIZATION
PETER GACS´
ABSTRACT. 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 plex anizes the cells in blocks that perform a reliable simula-
tion 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) anized 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 “anization”. The latter means that unless a large amount of input information
must be given, the initial configuration can be chosen homogeneous.
Date: May 5, 2005 (last printing).
1991 Mathematics Subject Classification. 60K35, 68Q80, 82C22, 37B15.
Key words and phrases. probabilistic cellular automata, interacting particle systems, renormalization, ergod-
icity, reliability, fault-tolerance, error-correction, simulation, hierarchy, anization.
Partially supported by NSF R-920484. The author also thanks the IBM Almaden Research Center
and the Center for Wiskunde and Informatica (Amsterdam) for their support during the long gestation of this
project.
1
2 PETER GACS´
CONTENTS
1. Introd