1
$\begingroup$

Sipser provided the following proof to prove the mapping reduction from $A_{TM}$ to $HALT_{TM}$, it in fact tried to build a mapping function:

enter image description here

My problem is the way this proof works. The function must take $<M,w> \in A_{TM}$ and produce $<M',w'>$ if and only if $<M',w'>\in HALT_{TM}$ We know by the hypothesis $<M,w>\in A_{TM}$. The machine $M'$ runs $M$ on an input $x$ not the input $w$. Now what if $<M,x>\notin A_{TM}$ and $<M,w>\in A_{TM}$? then $M'$ will output the loop while since $<M,w>\in A_{TM}$ the output must be accept. As a result the output $<M',w>$ which is supposed to be in $HALT_{TM}$ is not truly corresponded to the input. I would be appreciated if you explain about my problem.

Thanks

$\endgroup$
2
$\begingroup$

Your conception of a reduction is incorrect. The reduction takes an instance $\langle M, w \rangle$ of $A_{TM}$ and returns an instance $F(\langle M,w \rangle)$ of $HALT_{TM}$ such that $\langle M,w \rangle \in A_{TM}$ iff $F(\langle M,w \rangle) \in HALT_{TM}$.

Second, $M'$ is a Turing machine that accepts a single input $x$. The pair $\langle M',w \rangle$ belongs to $HALT_{TM}$ if $M'$ halts when running on the input $w$. Hence when analyzing whether $\langle M',w \rangle \in HALT_{TM}$ or not, the relevant value of $x$ is $w$.

Here is another way to think of the proof. Given a Turing machine $M$, we construct another Turing machine $M'$ such that $M$ accepts $w$ iff $M'$ halts on $w$.

When describing $M'$, we use $x$ to denote its input. There is no definite value of $x$ like your post seems to assume — it stands for the input to $M'$. For a similar example, consider the function $f(x) = x^2$. What is the value of $x$? It has no definite value, being just a place holder. If we plug in $w$ for $x$ then we get $f(w) = w^2$.

$\endgroup$
  • $\begingroup$ Thank you for your reply. From what I understand the $x$ has no definite value and it is just a placeholder. Is it true to say that the proof is right only if we plug in $w$ for $x$? As you stated in the last sentence. And why didn't the author run the $M'$ on $w$? $\endgroup$ – M a m a D Apr 30 '18 at 15:14
  • $\begingroup$ The proof is correct as stated. No need to change anything. $\endgroup$ – Yuval Filmus Apr 30 '18 at 15:19
  • $\begingroup$ The problem is I can't understand the relationship between $x$ and $w$ :( $\endgroup$ – M a m a D May 2 '18 at 7:21

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.