In the proof that $A_{\text{TM}}$ undecidable we use the following machine:

$D =$ On input $\langle M, w \rangle$:

  1. Simulate $M$ on input $w$.
  2. If $M$ ever enters its accept state, accept. If $M$ ever enters its reject state, reject.

But what will happen if change this so that the input is $\langle w \rangle^R$, that is, if we change the first step from what is written to:

  1. Run $H$ on input $\langle M, \langle M \rangle^R \rangle$

Another thing interests me (and unrelated to the previous modification) is what happen if we change the second step to be:

  1. If $H$ accepts, loop. If $H$ rejects, accept.

What I think based on reading the book "Introduction to the Theory of Computation" and notes:

  1. If only the first step changed like is written and input given to machine is $\langle M, \langle M \rangle^R \rangle$ machine can run and do comparison of $M$ on its reverse by the second time it visit the same letter and do comparison. Since $A_{tm}$ can be recognized by Turing machine, main problem of it not be able to decide is because $M$ loop on $w$. But in this case it is decidable because now instead of run on $\langle M, w \rangle$ it run on $\langle M, \langle M \rangle^R \rangle$ and algorithm can know Turing machine not halt on $\langle M, \langle M \rangle^R \rangle$ so it can reject it. because of it the machine is decidable after given change.
  2. Again, second question is on its own as if previous change not occur. This time, i am no sure. in case of $H$ accepting it loops and it seem like infinite loop. In case it rejects it accept? It seem not to be able to decide based on this change so it is still not decidable. It can not know if $M$ halt on given input $w$ because of infinite loop so it can not reject. So after change still not decidable.
  • $\begingroup$ Are you trying to solve some exercise? Or are you simply wondering what would happen under the modifications you have mentioned? $\endgroup$ – dkaeae Mar 26 '19 at 13:32
  • $\begingroup$ Also, you mention a "book" but do not name its title. It might be a good idea to do so, especially if you are citing text from it. $\endgroup$ – dkaeae Mar 26 '19 at 13:34
  • $\begingroup$ actually both. this is why i try to give my attempt so i can be also corrected or shown the right way. name of book :"introduction to theory of computation" $\endgroup$ – hpr16 Mar 26 '19 at 14:25
  • 1
    $\begingroup$ I have edited your question to make it easier to understand, but I believe there is room for much more improvement. I just happen to have Sipser's book (third international edition) on my desk and the construction you have cited for $D$ does not match the one in Sipser's book. (Incidentally, this explains the mysterious $H$ which pops up in your question's text.) Please edit the question so the citation is accurate. $\endgroup$ – dkaeae Mar 26 '19 at 15: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.