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

Question

如何用归约法证明语言的长度除以2？大号={ |是图灵机，其中 |L(M)|= 0 mod 2}

我有2个想法，但我怕跟错了一个 1) 我对 Amt 使用缩减方法，我说图灵机将 x=w0.....wi 作为输入，当且仅当 wi = 0 mod 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.

看看你能不能用它来减少费用。

您可以采用以下两种方法：

应用Rice's theorem立即得出该语言不可判定的结论，因为询问是否|L(M)|甚至是 RE 语言的重要属性。
使用 Recursion Theorem：构建一个 TM，询问其语言中是否包含偶数个字符串，如果答案是 "yes"，则选择不接受任何内容，如果是，则只接受空字符串答案是 "no." 这个 TM 的语言大小均匀当且仅当它不均匀时 - 自相矛盾！

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

Proving that a language's length is divided by 2 is undecidable

complexity-theory

turing-machines

decidable