A reader's guide to Gacs's "positive rates" paper

Lawrence F. Gray

Research output: Contribution to journalArticle

28 Scopus citations

Abstract

Peter Gacs's monograph, which follows this article, provides a counterexample to the important Positive Rates Conjecture. This conjecture, which arose in the late 1960's, was based on very plausible arguments, some of which come from statistical mechanics. During the long gestation period of the Gacs example, there has been a great deal of skepticism about the validity of his work. The construction and verification of Gacs's counterexample are unavoidably complex, and as a consequence, his paper is quite lengthy. But because of the novelty of the techniques and the significance of the result, his work deserves to become widely known. This reader's guide is intended both as a cheap substitute for reading the whole thing, as well as a warm-up for those who want to plumb its depths.

Original languageEnglish (US)
Pages (from-to)1-44
Number of pages44
JournalJournal of Statistical Physics
Volume103
Issue number1-2
DOIs
StatePublished - Apr 1 2001

Keywords

  • Cellular automaton
  • Error-correction
  • Phase transition
  • Self-simulation
  • Stability
  • Universal computation

Fingerprint Dive into the research topics of 'A reader's guide to Gacs's "positive rates" paper'. Together they form a unique fingerprint.

  • Cite this