# Proving $A_{TM}$ is mapping reducible to certain language

I've been asked to prove that the language $$A_{TM} = \{ \langle M,w\rangle \mid M$$ is a TM that accepts $$w\}$$ is mapping reducible to the language $$LOOP-ONE = \{\langle M \rangle \mid M$$ is a Turing machine that doesn't halt on exactly one input$$\}$$.

I came up with the following idea :

F = "On input <M,w>:

1. Construct the following machine M':
M' = "On input x:
1.If $$x=w \cdot 1$$, enter a loop. (assuming $$1 \in \Sigma$$ )
2.Run M on w.
3.If M accepts, accept. otherwise, enter a loop."
2. Output <M'>."

As for the correctness of the reduction above we can see that :
If $$ \in A_{TM} \implies M$$ accepts $$w$$ therefore by the construction above $$M'$$ accepts any input $$x$$ (besides $$w\cdot1$$) therefore in particular $$M'$$ halts on any input other than $$w\cdot1$$.
On the other hand,
If $$ \notin A_{TM} \implies M$$ doesn't accepts $$w$$ therefore $$M$$ either loops on $$w$$ or rejects $$w$$.
If $$M$$ loops on $$w$$ then $$ \notin LOOP-ONE$$ as $$M'$$ doesn't halts on $$w$$ and on $$w\cdot1$$.
If $$M$$ rejects $$w$$ then $$M'$$ will loop on any input $$x$$ and therefore $$ \notin LOOP-ONE$$.

I was asked to make sure that the function that the TM F is computing is indeed computable, and I'm struggling to see what it practically means. What are the things that make a mapping reduction not computable (besides maybe the fact that the Turing machine F may not halt on some input, which is not the case here) ?

For a reduction $$f$$ to be computable, there must be a TM that for all inputs $$y$$ halts with $$f(y)$$ written on its tape. The reduction you suggested is indeed computable. Here, your input $$y$$ is assumed to be of the form $$\langle M, w \rangle$$, then the reduction outputs a description of a machine $$\langle M'\rangle$$. The crux of the idea here is to notice that the reduction $$f$$ (or the machine that tries to implement it) does not really simulate the run of $$M$$ on $$w$$, and does not simulate the run of $$M'$$ on some input. It just outputs the description of $$M'$$ and then halts. So you only need to convince the reader that there is a TM $$T_{f}$$ that can output the description of $$\langle M'\rangle$$ based only on the description of $$\langle M, w\rangle$$, and then halt. This is doable as you can take the description of $$M'$$ to be a description of a universal TM that has the description of $$M$$ and $$w$$ encoded in it (for example in its state-space). Also $$M'$$ has a state $$q_{loop}$$ that forces it to inter a loop. Then, on input $$x$$, what $$M'$$ should be able to do is:
• Simulate the run of $$M$$ on $$w$$: we can describe also this component (or part) of the machine $$M'$$ similarly to the description of a universal TM.
• Enter a loop: we can encode the transition function of $$M'$$ to enter $$q_{loop}$$ in some scenarios.
So the main thing here is to note that the description of $$M'$$ can be obtained by manipulating the description of $$M$$ and $$w$$ and putting that together with a description of universal TM that does simple checks. So you can think of $$M$$ ia a python code, and $$w$$ is its input. Then, you (the reduction), given this code and input, have to output a python code $$M'$$ that behaves in a way that depends on $$M$$ and $$w$$. That is doable, as long as you (the reduction) sew the codes together without really running them, and so the risk of you non-halting is avoided.