0
$\begingroup$

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:

  1. Run H on $<M,<M>>$.
  2. If H accepts then reject.
  3. 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>$:

  1. Simulate M on $<M>$
  2. 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.

$\endgroup$
  • $\begingroup$ In MathJax you need to use \{ ... \} (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$ – D.W. Mar 31 at 16:12
  • $\begingroup$ thank you very much for fixing it for me. i am new here and i am doing my best to make my questions be the best they can. could you please also help me with the given question? $\endgroup$ – hps13 Mar 31 at 17:57
  • $\begingroup$ Aside from the input $\langle M, \langle M \rangle \rangle$ (which should be just $\langle M \rangle$), I don't see anything wrong with your proof. You said you were having a "problem". Well, what is it? $\endgroup$ – dkaeae Apr 3 at 15:41
  • $\begingroup$ i wasn't sure i did it correctly. i guess lack of self belief? $\endgroup$ – hps13 Apr 4 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.