1 
L = { <M> | M is a Turing machine over {0, 1}, and <M>||<M> (not in) L(M)}

如何证明 L 不可识别？有任何想法吗？

我已经证明L compliment是可识别的：

Set Turing machine to J 
1. Run J on input <M>||<M>
2. TM J accepts then accept, it reject the reject.

<M>||<M> is the concatenation of the encoding of the Turing machine.
4

1 回答 1

1

您可以将（对角线）接受问题简化为这个问题。我尝试使用你自己的符号

D = { <M> | M is a Turing machine over {0, 1}, and <M> (not in) L(M)}

假设修复机器 M 的编码，并考虑一个新程序，它接受输入字符串 w 并接受它以防万一<M> in L(M)（因此它具有恒定的行为，独立于输入字符串，并且仅依赖于<M>）。前面的程序可以参数化和有效地构建<M>，也就是说，我们有一个总的可计算函数 h 使得前面的程序有代码 h(<M>)。形式上，我在这里使用 smn 定理，但由于我不确定你是否对此有信心，所以我不想提及它。

现在的问题是如果h(<M>) is in L。

如果<M> in D，那么通过构造机器h(<M>)不接受任何字符串，特别是不接受h(<M>)||h(<M>)，所以h(<M>)在 L.

相反，如果<M> not in D，则通过构造，机器h(<M>)确实接受任何字符串，特别是它接受h(<M>)||h(<M>)，所以h(<M>)不在 L 中。

如果我们有办法决定 L，我们就有办法决定 D，而且我们知道 D 是不可判定的（事实上，它是生产性的，类似于 L）。

于 2017-01-22T09:13:50.620 回答