0
$\begingroup$

In Sipser, there is a proof I don't understand.

First he established the undecidability of $A_\mathrm{TM}$, the problem of determining whether a Turing machine accepts a given input.

$$A_\mathrm{TM}=\left\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ accepts }w\right\}\,.$$

Then defined $\mathrm{HALT_{TM}} = \left\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ halts on input }w\right\}$, he assume that $\mathrm{HALT_{TM}}$ is decidable and use that assumption to show that $A_\mathrm{TM}$ is decidable, contradicting.

He assume that we have a TM $R$ that decides $\mathrm{HALT_{TM}}$. Then he uses $R$ to construct $S$:

$S$ = "On input $\left \langle M,w \right \rangle$, an encoding of a TM $M$ and a string $w$:

  1. Run TM $R$ on input $\left \langle M,w \right \rangle$.
  2. If $R$ rejects, reject
  3. If $R$ accepts, simulate $M$ on $w$ until it halts.
  4. If $M$ has accepted, accept; if $M$ has rejected, reject."

He says "Clearly, if $R$ decides $\mathrm{HALT_{TM}}$, then $S$ decides $A_\mathrm{TM}$. Because $A_\mathrm{TM}$is undecidable, $\mathrm{HALT_{TM}}$ also must be undecidable."

I don't understand why is so obvious the problem is $R$. I mean, I don't understand why if $R$ exists, then inevitably we can simulate $M$. We know that the step number 4 is not possible because $H(\left \langle M,w \right \rangle)$ = "accept if $M$ accepts $w$ OR reject if $M$ rejects $w$" is not possible, so why is $R$ guilty?

$\endgroup$
  • $\begingroup$ $M$ can be simulated regardless of the existence of $R$. But if $R$ tells you that $M$ halts on input $w$, you can be sure that the simulation of $M$ will either accept or reject the input $w$, so you can decide if $\langle M,w\rangle$ is in $A_{TM}$ or not. $\endgroup$ – Jasper Jul 2 '14 at 11:49
3
$\begingroup$

Step one, don't try to argue why this TM can not work: under the assumption it does work. But then, since everything else $S$ does is possible (you have to accept that separately), the existence of $R$ certainly is "the problem".

As for understanding, the proof, there are two facts you have to check (under the assumption that $R$ exists):

  1. $S$ is a Turing machine (i.e. its function is computable)
  2. $S$ decides $A_{TM}$.

Arguably, 1) is clear; simulating other TMs given their indices/encodings is something TMs can do (thanks to the existence of a universal TM, which you should have seen a proof of already) and $S$ does little more. This is as close to a proof as you'll get with this form of "definition" of $S$; it's more of an idea, really.

For the second, note that $S$ always halts because $R$ always halts and

$\qquad\begin{align*} S\langle M,w \rangle) = 1 &\iff R(M,W) = 1 \land M(w) = 1 \\ &\iff M(w)\downarrow \land M(w) = 1 \\ &\iff w \in L_M \\ &\iff \langle M,w \rangle \in A_{TM} \;. \end{align*}$

By definition, that means that $S$ decides $A_{TM}$.

Similar arguments usually works for this kind of proof; check our reference questions and other questions tagged .

$\endgroup$
  • $\begingroup$ Ok, I understand. If R exists, then for sure is decidable. Ok, thank you. $\endgroup$ – Pedro Jul 2 '14 at 15:40
  • $\begingroup$ M can be simulated, but an other thing is accepting or rejecting w. I see now. $\endgroup$ – Pedro Jul 2 '14 at 15:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.