摘要
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.
摘要译文
关于图灵机M的输入 - 输出行为的真实断言可能独立于（即，不可能证明）理论T，因为M的计算行为特别不透明，或者因为M计算的函数或集合本质上是微妙。后一种与表征无关的独立结果更令人满意。对于π2断言，证明独立性的最着名的技术当然会产生与表示无关的结果。本文通过证明集合S和R类的非常弱的条件保证存在集合L0εR - S使得L 0可能不是无穷大（因此，不可证明是非正规的）来说明当前对π2断言的不可证明性的理解。 ，非确定性，非无文本，不在P等，等等。在稍强的条件下，可以在每个LεR - S内找到这样的L 0。
Stuart A.Kurtz[∗];Michael J.O'Donnell;James S.Royer;. How to prove representation-independent independence results[J]. Information Processing Letters, 1987,24(1): 5-10