Reliable Computation with Cellular Automata.
Abstract
In this document the author constructs 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 mechanics, 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. To compute reliably 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 organiozation 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. Additional keywords: Data Storage Systems, Problem Solving.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1985
- Accession Number
- ADA150656
Entities
People
- P. Gacs
Organizations
- University of Rochester