如何證明以下語言不可判定？

Question

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. 

Answer 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>)不接受任何字符串，特別是不L.

相反接受h(<M>)||h(<M>)，所以h(<M>)，如果<M> not in D，再由施工機械h(<M>)不接受任何串，特別是它接受h(<M>)||h(<M>)，所以h(<M>)不L.

如果我們有辦法來決定L，我們將有一個方式來決定d，而我們知道，d是不可判定（事實上，它是有生產力的，類似於L）。