Reliable computation with cellular automata

摘要

We construct a one-dimensional array of cellular automata on which arbitrarily large computations can be implemented reliably, even though each automaton at each step makes an error with some constant probability. In statistical physics, this construction leads to the refutation of the “positive probability conjecture,” which states that any one-dimensional infinite particle system with positive transition probabilities is ergodic. Our approach takes its origin from Kurdyumov's ideas for this refutation. To compute reliability with unreliable components, von Neumann proposed Boolean circuits whose intricate interconnection pattern (arising from the error-correcting organization) he had to assume to be immune to errors. In a uniform cellular medium, the error-correcting organization exists only in “software,” therefore errors threaten to disable it. The real technical novelty of the paper is therefore the construction of a self-repairing organization.