L = { <M> | M is a Turing machine over {0, 1}, and <M>||<M> (not in) L(M)}
How do I prove that L is not recognizable? Any ideas?
I've proven the L compliment
is recognizable:
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.
You can reduce the (diagonal) acceptance problem to this problem. I try to use your own notation
Suppose to fix an encoding of machine M, and consider a new program that takes in input a string w and accepts it just in case
<M> in L(M)
(so it has a constant behaviour, independent from the input string, and only dependent on<M>
). The previous program can be build parametrically and effectively in<M>
, that is we have a total computable function h such that the previous program has codeh(<M>)
. Formally, I am using the smn theorem here, but since I am not sure you are confident with it, I prefer not mentioning it.Now the question is if
h(<M>) is in L
.If
<M> in D
, then by construction the machineh(<M>)
does not accept any string, and in particular does not accepth(<M>)||h(<M>)
, soh(<M>)
in L.Conversely, if
<M> not in D
, then by construction the machineh(<M>)
does accept any string, and in particular it acceptsh(<M>)||h(<M>)
, soh(<M>)
not in L.If we had a way to decide L, we would have a way to decide D, and we know that D is not decidable (in fact, it is productive, similarly to L).