# Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$

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: 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

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$.
• 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$? – M a m a D Apr 30 '18 at 15:14
• The problem is I can't understand the relationship between $x$ and $w$ :( – M a m a D May 2 '18 at 7:21