I want to solve the following exercise in Computability and Complexity Theory:

By providing a reduction from the HALTING problem to REACHABLE-CODE, prove that REACHABLE-CODE is undecidable.

REACHABLE-CODE is defined like this:

INSTANCE: A source code S, a number n of a line in S. QUESTION: Is there an input I for S such that the run of S on I will reach the code on line n?

I am not sure how to solve this. Can i Solve this by assuming that ther IS an algorithm for the REACHABLE-CODE problem and use it as a subroutine in an alrogithm that solves the HALTING problem?

  • 2
    $\begingroup$ Why do people keep tagging questions about deciability with [decision-theory]? $\endgroup$ – Asaf Karagila Apr 12 '13 at 15:36
  • $\begingroup$ @AsafKaragila: My guess: because there isn't a "decidability" tag. If you start typing "deci", the only options are "decimal-expansion" and "decision-theory", so for someone who doesn't what decision theory is, the latter seems closer to "theory of decidability". (But I guess you knew this already, and your question wasn't intended to be taken literally.) $\endgroup$ – ShreevatsaR Apr 12 '13 at 15:39
  • $\begingroup$ @ShreevatsaR: Obviously my question was meant as a rhetorical rant... ;-) $\endgroup$ – Asaf Karagila Apr 12 '13 at 15:40
  • 1
    $\begingroup$ @AsafKaragila: Why not create a decidability tag, and have redirect it to computational-complexity or whatever? $\endgroup$ – ShreevatsaR Apr 13 '13 at 13:21

Yes, that is what it means to reduce one problem to another: you assume you have an algorithm for the reachable code problem, and show that this would allow you to build an algorithm for 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.