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. ....."


$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?

  • $\begingroup$ "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. $\endgroup$ – Raphael Jun 22 '16 at 14:37
  • $\begingroup$ 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. $\endgroup$ – Cheiron Jun 22 '16 at 14:51

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.