Using reductions of turing machines properly

Question

I recently learned about reductions of Turing machines (here after TM), and here is a solution to a problem using reduction (showing L is undecidable, as defined bellow). I have given the reduction, correctness proof and my understanding of it. I'm fairly certain it is correct, but I have found multiple times that with problems in Theory of Computation it is easy to misunderstand things. So I would greatly appreciate anyone's feedback!. (If this question is not suitable here please let me know where I should post!)

Suppose I want to reduce Htm to L, where Htm = { M, w | M halts on w} and L = { M | M is a TM, and M halts on all inputs of length at most 2016}

I then then define

f = on input (w, M), where w is a string, and M a TM

1. Construct the following TM, X

   X =" on input y

   1. Simulate M on w
   
   2. if (the simulation accepts or rejects) accept
   

2. return X

Correctness is proved as follows: if (w, M) is in Htm, then X is in L, since in line 2 of X it will accept all strings. if (w, M) is not in Htm, then X will simply sloop, and thus will never halt which implies X is not in L.

If I understood correctly, when performing a reduction, you essentially use the input, in this case (w, M) and then transform it. So in this case, X is define in such a way that if its simulation halts (i.e. it accepts or rejects) it will halt (by accepting) but if the simulation of M on w does not halt, then X will never reach line 2, so essentially it will not halt for any inputs. In particular, it will not halt on any inputs of length of at most 2016.

Answer 1

As noted by Andreas, the reduction the OP is asking about is a many-one reduction or a mapping reduction (Sipser)

A language/problem A is mapping-reducible to a language/problem B if a function $f$ exists such that,

$w \in A \iff f(w) \in B$

In your example:

$H_{tm}$ is $A,\;$ $L$ is $B$

To prove your reduction, you would have to show:

$<M, w> \;\in H_{tm} \iff f(<M, w>) \in L$

You have done that because you have shown:

$<M, w> \;\in H_{tm}$
$\Rightarrow M$ halts on $w$
$\Rightarrow f(<M, w>)$ accepts all inputs
$\Rightarrow f(<M, w>) \in L$

and that

$f(<M, w>) \in L$
$\Rightarrow M$ halts on $w$
$\Rightarrow <M,w> \;\in H_{tm}$