Reliable Cellular Automata With Self-Organization

Abstract

In a noisy cellular automaton, even if it is infinite, it is nontrivial to keep a bit of information for more than a constant number of steps. A clever solution in 2 dimensions has been applied to a simple 3-dimensional fault-tolerant cellular automaton. This technique did not solve the following problems: remembering a bit of information in 1 dimension; computing in dimensions lower than 3, or with non-synchronized transitions. With a more complex technique using a hierarchy of simulations, we construct an asynchronous one-dimensional reliable cellular automaton, which is also "self-organizing". This means that if the input information has constant size, the initial configuration can be homogenous: the hierarchy organizes itself. An application to information storage in positive-temperature Gibbs states is also given.