I have a problem proving the following properties of given language K:
$K = \{< M > | M\ accepts < M >\}$
I am trying to prove that language K is Turing-recognizable but undecidable using the diagonalization method.
What I tried regarding proving K is undecidable using diagonalization:
Suppose there exists a Turing machine H that decides K, denoted by H. Then H accepts if M accepts M and rejects in any other case, for any input $<M,<M>>$,so if D is a Turing machine that negates diagonals, then we construct it as following:
- Run H on $<M,<M>>$.
- If H accepts then reject.
- If H rejects then accept.
We deduce that D is a decider because H is a decider, so D on $<D>$ - accept, but: $H<D,<D>>$ - reject, so it makes D on $<D>$, reject and that's a contradiction, so language K is undecidable.
Proving K is Turing-recognizable:
Constructing a recognizer H for K: on input $<M,<M>$:
- Simulate M on $<M>$
- If M accepted - accept. if M rejected - reject.
So if $<M> \in K$ then M run on $<M>$ and halt in accept state, and if not in K, then just reject it or loop.
Would very appreciate your input and explanations on how to show it is not turing decisive using the diagonalization method. Tried to do my best and prove it the best I could.
\{ ... \}
(i.e., backslashes) to write a set, not{ ... }
. I fixed it for you, but letting you know for the future. Also,\langle ... \rangle
looks better than< ... >
. $\endgroup$