0
$\begingroup$

i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book).

on page 207 of the book "introduction to the theory of computation", there's a proof that $A_{TM}$ is not decidable.

the proof is constructed using contradiction, while assuming there's a machine $H$ that is a decider for $A_{TM}$ and takes input of $\langle M,w\rangle$ where $M$ is a turing machine and $w$ is a string, and H halts and accepts if $M$ accepts $w$, and assuming that $H$ halts and rejects if $M$ fails to accepts $w$.

then, they construct a new turing machine $D$ with $H$ as a subroutine that does the following:

$D$ = "On the input $\langle M\rangle$ where $M$ is a TM:

  1. Run $H$ on input $\langle M,\langle M\rangle\rangle$
  2. Output the opposite of what $H$ output. that is, if $H$ accepts, reject; and if $H$ rejects, accept.

the questions: will the proof still hold true if we change the following changes independently, i.e., each change is separate and does not affect the other separate situation:

1) if we change step 1 so that it will be: Run $H$ on input $\langle M,\langle M\rangle^R\rangle$,

2) if we change step 2 so that it will be: If $H$ accepts, loop. if $H$ rejects, accept.

my attempt:

1) the proof will remain true, because we are proving by contradiction that on machine $D$, running $H$ as a subroutine will not allow us to decide $A_{TM}$. furthermore, running $D$ with input of itself, i.e $D(\langle D\rangle)$, forces the machine to do the opposite, thus creating the contradiction. so it doesn't matter if we run $D(\langle M\rangle)$ or $D(\langle M\rangle^R)$, the result will be the same when we run $D(\langle D\rangle)$ and the $D$ will be forced to decide the opposite(accept if not accept $\langle D\rangle$ and reject if $D$ accepts $\langle D\rangle$).

2) well, here i am not sure. because in the original proof if $H$ accepts, then it reject, and if $H$ rejects, then it accepts. now if we say "If $H$ accepts, loop. if $H$ rejects, accept", well, we have a problem, because now $H$ Halts and then it is decided, even though incorrect. the loop is the main problem here and i hope i interpreted it right.

have i done it correctly? i am really not sure, especially regarding 2. is it enough to be an acceptable explanation?

thank you very much for helping. did my best to elaborate it and fixing the question in the site that lacks correct information from the book (also gave sources from it).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Admittedly, I'm very new at this but since your new #2 loops then D is no longer a decider. Thus the proof wouldn't hold. That's my intuition anyway. Someone else will correct me(us) :) $\endgroup$
    – user6882
    Apr 8, 2019 at 1:12
  • $\begingroup$ thank you very much for your comment. i really hope someone will correct us and show us the correct way, but i definitely agree with you $\endgroup$
    – hps13
    Apr 8, 2019 at 9:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.