# When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I create $M'$ in such a way that the next step is depended upon whether or not a simulation stops? Take the following two examples:

$M' =$ "on input $M, w$:

1. Simulate $M$ on input $w$. If $M$ stops, go to step 2. Else: go to step 3.
2. ....
3. ....."

And

$M'' =$ "on input $M, w$:

1. ...
2. Run $M$ on input $w$.
3. accept."

The first one requires the decider for $S$ to solve $\mathrm{HALT}_{\mathrm{TM}}$ more explicitly then the second one. Is the first one wrong?

• "For this I need to build a new Turing machine, M′." -- depends. You need to create an instance of the new problem $S$ which may or may not include a TM. – Raphael Jun 22 '16 at 14:37
• That is true, but I was specifically refering to languages that talk about TM's. Therefore the statement: I need to build a new TM M' holds in many cases. – Cheiron Jun 22 '16 at 14:51

But the main point is that your reduction looks backwards. You're supposed to be using the argument "$S$ must be undecidable because I could use the ability to decide $S$ to let me decide the halting problem, which is impossible." But, by basing decisions on whether some Turing machine halts or not, you're assuming that you can determine this, i.e., assuming that you can already decide the halting problem.