1
$\begingroup$

This Problem sparked my question: Does a TM $M$ enter state $q$ on input $w$?

I proved it was undecidable in this format using the Halting Problem as a subroutine:

If HALT simulate M on w and return result else return false

Since HALT is undecidable, this given problem is undecidable as well.

However, the given solution proved in the opposite way, by creating a decider for the problem, and using it as a subroutine to solve the Halting Problem.

Is my direction of the proof still valid, and can my approach be used to prove other undecidable problems (using a known undecidable problem as a subroutine rather than the other direction)?

$\endgroup$
1
$\begingroup$

When proving decidability of a new problem, you reduce the new problem (i.e. a problem with unknown solution) to an old one (used as subroutine) with a known solution, so that the techniques used to solve the old one can be used to solve the new one.

But, when proving undecidability, you have to do the opposite. You reduce the old problem, known to be undecidable, to the new problem (used as subroutine), in such a way that, if the new problem has a decision procedure, its use as a subroutine provides a decision procedure to the old problem, known not to have any. Hence the new problem cannot have a solution, and is undecidable.

In your example, you should have tried to show that if you have a decision for your new problem, that you can use as subroutine, then you ave a decision for the halting problem, which is not possible.

So proofs go both ways only in the sense that the contrapositive of a statement goes the other way. Decidability goes one way, and undecidability goes the other way.

However, it you can do the reduction both ways at the same time (either both for decidability or both for undecidability), then you have proved that the two problems are strictly equivalent, and that any solution for one is a solution for the other. When it goes only one way, this establishes that one problem is harder than the other (letting you work out which is which).

I guess that is about all I can say about the "direction"of the proof.

$\endgroup$
  • $\begingroup$ Thank you, i think this a very good answer to my question. I actually have not learned about the concept of hardness for a problem quite yet. Just to summarize/simplify your answer: When proving decidability of a new problem, you use an old decidable problem as a subroutine to solve the new problem, to show that the new problem is decidable. When proving undecidability of a new problem, you use the new problem as a subroutine to solve the old problem, to show that the new problem is undecidable, because the old one was undecidable. Is this a correct summary? $\endgroup$ – ajoseps Jun 7 '15 at 20:37
  • $\begingroup$ and to clarify, by subroutine, you mean like if statements in traditional code right? $\endgroup$ – ajoseps Jun 7 '15 at 20:38
  • $\begingroup$ @dbcs I do not use the word subroutine in my own proofs, but I noticed some people do, including yourself in the question. I guess it does correspond to an "if" statement, on a condition that is actually to be disproved,as the subroutine is used "if one assumes it can be used effectively". And since that leads to a contradiction ... the assumption must be false (for undecidability proofs). What you use as subroutine is either a decidable problem to decide another one, or a problem that you are trying to prove as hard as another one. $\endgroup$ – babou Jun 7 '15 at 20:44
  • $\begingroup$ I've actually noticed (while researching this question as well as many others) that you answer a lot of these in this subject are. Thank you for doing so! $\endgroup$ – ajoseps Jun 7 '15 at 21:16

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.