# Proving By reduction from the Halting Problem

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?

-
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