### 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 L_{0} ε R - S such that L_{0} is not probably infinite (hence, not provably nonregular, nondeterministics, noncontext-free, not in P, etc.). Under slightly stronger conditions, such L_{0}'s may be found within every L ε R - S.

Original language | English (US) |
---|---|

Pages (from-to) | 5-10 |

Number of pages | 6 |

Journal | Information Processing Letters |

Volume | 24 |

Issue number | 1 |

DOIs | |

State | Published - Jan 15 1987 |

### 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

*Information Processing Letters*,

*24*(1), 5-10. https://doi.org/10.1016/0020-0190(87)90191-8