L = { <M> : TM 不接受任何东西 }

Question

L = { <M> : TM does not accept any thing }

只要TM接受，我们就可以一个一个的给TM输入字符串。如果没有这样的字符串，那么这个过程将无限期进行下去，所以我们无法决定。因此 Recursive Enumerable。

P = { <M> : TM accept atleast one string }

我们可以说它是半可判定的。只要 TM 至少接受一个字符串，我们就可以将字符串一个一个地输入到 TM 中。但是这个过程可以无限期进行并且不能保证 TM 会停止，因此 Recursive Enumerable.
如果以上两种逻辑都是正确的，那么 L 和 P（两者相互补充）如何同时递归枚举。

If L and P are complement to each other and both are Recursive Enumerable then L must be Recursive.

我哪里错了？？

Answer 1

你错了 L 是半可判定的。

P 是半可判定的，如果我们小心地给它输入字符串。见以下伪代码

i <- 0;
while (true) {
    foreach x in combanitaions of alphabet, such that |x| <= i {           (\Sigma^*)
        if (Simulate M for up to i steps == Accept) {
            Accept;
        }
    }
    ++i
}

如果M接受至少一个字符串，总有一天我们会找到它，因此P（实际上NONEMPTY）是半推导的。

NONEMPTY 是不可推导的，这可以从通用语言 (Lu) 被简化为 NONEMPTY

中看出

Lu = { <M,x> | x ∊ L(M) }

并且 Lu <= NONEMPTY 成立（稍后可以添加证明）。由于 Lu 不可推导，因此 NONEMPTY 也不可推导。

因此，根据 Post 定理，NONEMTPY（您的 L）的补集甚至不能半推导。

Answer 2

简答：L 不是 RE。

要成为 RE，您必须能够在有限时间内确定语言中的 string/TM IS。你们确定不满足此要求的技术；它允许您确定 string/TM 在有限时间内不在该语言中（通过查找 TM 将接受的输入），但由于 TM 不需要停止在不被接受的字符串上，因此它可能永远不会因任何未接受的字符串而停止。因此，它是co-RE，这就是为什么它的赞美是RE（"co"是"complementary"的缩写）。

请注意，一种语言及其补语可能都是 RE：交集将是一种可判定的语言。

L = { <M> : TM 不接受任何东西 }

L = { <M> : TM does not accept any thing }

computation-theory

turing-machines

computation

tableofcontents