Reliable computation with cellular automata
type: Item
instance of: scholarly article
title: Reliable computation with cellular automata
zbMATH Open document ID: 0621.68038
DOI: 10.1016/0022-0000(86)90002-4
author: Peter Gács
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
full work available at URL: http://hdl.handle.net/1802/8851
review text: 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.
Mathematics Subject Classification ID: 68Q80
zbMATH DE Number: 4007732
zbMATH Keywords: reliable computation with unreliable components
zbMATH Keywords: one-dimensional cellular space
zbMATH Keywords: k-dimensional cellular space
zbMATH Keywords: ergodicity
zbMATH Keywords: stability
zbMATH Keywords: positive probability conjecture
zbMATH Keywords: error-free medium
zbMATH Keywords: error-correcting medium
MaRDI profile type: Publication
OpenAlex ID: W2078058516
cites work: Q4156682
cites work: Q4174769
cites work: Q3293678
cites work: A stability criterion for attractive nearest neighbor spin systems on Z
cites work: Fault tolerant cellular automata
cites work: Q4184052
cites work: Q4137895
cites work: Fault tolerant cellular spaces
cites work: Reliable Computation in Computing Systems Designed from Unreliable Components*
cites work: Q3883500
cites work: Q3322031
cites work: A natural modification of a random process and its application to stochastic functional series and Gaussian measures
description: scientific article; zbMATH DE number 4007732