Reliable computation with cellular automata (Q1090457): Difference between revisions

The paper under review can be included among those searching for ways to perform reliable computation with unreliable components. The author reaches this goal for computation done by one-dimensional cellular space whose automaton-component makes at each step an error with constant probability. As a consequence of the construction proposed, the ''positive probability conjecture'' considered in statistical physics may be considered rejected. A k-dimensional cellular space (medium) is lattice of automata in \({\mathbb{Z}}^ k\). All automata are identical with respect to their function and connection to their relative neighbors; they are unreliable in the sense that they can make an error at each step with some constant probability. The medium is working in discrete time. Two features of such media are of interest: ergodicity and stability. A. L. Toom has constructed a 2-dimensional stable nonergodic medium. The first attempt to build a 1-dimensional stable nonergodic medium was made by \textit{G. L. Kurdyumov} [Dokl. Akad. Nauk SSSR 238, 1287-1290 (1978; Zbl 0399.60098)]. He suggested a construction using a hierarchy of Turing machine-like media, simulating each other. The paper under review is partially based on Kurdyumov's ideas. It has the goal to prove two theorems: the first one is meant to refute the ''positive probability conjecture''; the second one supplies the construction which allows defining for each ideal error- free medium U one ''physical'' error-correcting medium simulating U in such a way that the probability of deviations remains under control (in fact, the first theorem is non-immediate consequence of the second one). The proof is rather complicated and is performed in a ''main-stream'' manner, introducing secondary items and proving ''technical'' lemmas after establishing the central result.