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 $&lt;M,w&gt; \in A_{TM}$ and produce $&lt;M',w'&gt;$  if and only  if $&lt;M',w'&gt;\in HALT_{TM}$ We know by the hypothesis $&lt;M,w&gt;\in A_{TM}$. The machine $M'$ runs $M$ on an input $x$ not the input $w$. Now what if $&lt;M,x&gt;\notin A_{TM}$ and $&lt;M,w&gt;\in A_{TM}$? then $M'$ will output the loop while since $&lt;M,w&gt;\in A_{TM}$ the output must be accept. As a result the output $&lt;M',w&gt;$ 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 &mdash; 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$.