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$:
- Simulate $M$ on input $w$. If $M$ stops, go to step 2. Else: go to step 3.
- ....
- ....."
And
$M'' = $ "on input $M, w$:
- ...
- Run $M$ on input $w$.
- 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.
Question Source : http://cs.stackexchange.com/questions/59905
0 comments:
Post a Comment
Let us know your responses and feedback