complexity-theory - 证明语言的长度除以 2 是不可判定的

Question

如何使用缩减方法证明语言的长度除以 2？L={ | 是一个图灵机，其中 |L(M)|= 0 mod 2}

我有 2 个想法，但我害怕遵循错误的想法 1）我使用 Amt 的归约方法，我说图灵机将 x=w0.....wi 作为输入并接受当且仅当 wi = 0 模 2 。

2）我用NOT HALT的归约法，我说图灵机会拒绝任何输入，所以图灵机的长度为0，满足上面的条件！

有什么建议吗？

Answer 1

这是一种选择。给定一个 TM M 和一个字符串 w，构建这个新的 TM N：

N = "On input x:
        If x isn't the empty string, reject.
        Otherwise, run M on w.
        If M accepts, accept; if M rejects, reject.
        (Implicitly, if M loops on w, N loops on x.)"

这个 TM 有一个性质，如果 M 接受 w，那么 L(N) = {ε}，所以 |L(N)| = 1。否则，如果 M 不接受 w，则 L(N) = ∅，所以 |L(N)| = 0。

看看你是否可以在减少中使用它。

以下是您可以采取的另外两种方法：

1. 应用赖斯定理立即得出结论，这种语言是不可判定的，因为询问是否 |L(M)| is even 是 RE 语言的一个重要属性。
2. 使用递归定理：构建一个 TM，询问其语言中是否包含偶数个字符串，如果答案为“是”，则选择不接受任何内容，如果答案为“否”，则选择不接受空字符串。当且仅当它没有时，该 TM 的语言具有均匀的大小 - 矛盾！