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
我是NDTM的新手，但我理解圖靈機的概念。當談到NDTM我變得有點困惑，我米應該制定一個對語言NDTM {A，B，C}和 L = {w ∈ Σ*| Ǝv ∈ Σ*, Ǝn >= 2 with w = v (to the power of) n }
，我想知道 的第一件事是如何讀取L，例如Ǝ的含義是什麼？ 我的確瞭解NDTM給出了一種結果的兩種可能性，比如對於一個： ，如果我是正確的，我們可以使
想象我有一個圖靈機屬性，看起來像這樣： P = {M | L(M) is accepted by a Turing machine that does not halt in an even number of steps for any input}
我如何證明這個屬性是小事？或者更一般地說，有沒有很好的方法來證明這種事情？