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