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

Problem Detail: 

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?

Asked By : Cheiron

Answered By : David Richerby

No, you can't.

First, as a technical point, it never makes sense to say "If this simulation halts", since that would require doing the whole simulation and, if it doesn't halt, you'd never finish simulating it. You can, in certain circumstances, ask whether a particular Turing machine halts on a particular input, but that's something subtly different.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59905

3200 people like this

 Download Related Notes/Documents