Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Why do people keep tagging questions about deciability with [decision-theory]? – Asaf Karagila Apr 12 '13 at 15:36
@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.) – ShreevatsaR Apr 12 '13 at 15:39
@ShreevatsaR: Obviously my question was meant as a rhetorical rant... ;-) – Asaf Karagila Apr 12 '13 at 15:40
@AsafKaragila: Why not create a decidability tag, and have redirect it to computational-complexity or whatever? – ShreevatsaR Apr 13 '13 at 13:21
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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