How to prove representation-independent independence results

Stuart A. Kurtz, Michael J. O'Donnell, James S. Royer

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

A true assertion about the input-output behavior of a Turing machine M may be independent of (i.e., impossible to prove in) a theory T because the computational behavior of M is particularly opaque, or because the function or set computed by M is inherently subtle. The latter sorts of representation-independent independence results are more satisfying. For π2 assertions, the best-known techniques for proving independence yield representation-independent results as a matter of course. This paper illustrates current understanding of unprovability for π2 assertions by demonstrating that very weak conditions on classes of sets S and R guarantee that there exists a set L0 ε R - S such that L0 is not probably infinite (hence, not provably nonregular, nondeterministics, noncontext-free, not in P, etc.). Under slightly stronger conditions, such L0's may be found within every L ε R - S.

Original languageEnglish (US)
Pages (from-to)5-10
Number of pages6
JournalInformation Processing Letters
Volume24
Issue number1
DOIs
StatePublished - Jan 15 1987
Externally publishedYes

Keywords

  • Independence
  • formal logic
  • subrecursive complexity classes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'How to prove representation-independent independence results'. Together they form a unique fingerprint.

Cite this