Reachable Code Problem

computation

Definition

Reachable Code Problem

The reachable code problem is a decision problem that asks, for a given program $\Pi$ and a natural number $n$, whether there exists an input $i$ for program $\Pi$ such that the code with line number $n$ is executed when running $\Pi$ with input $I$.

Semi-Decidability

The reachable code problem is semi-decidable.

A recogniser can enumerate candidate inputs $I$ and simulate the program $\Pi$ on $I$ for increasing time bounds $k\in \mathbb{N}$. If, during any simulation, the execution reaches line $n$, the procedure halts and answers true.

More formally, the following search procedure recognises positive instances:

$$\text{for }I\in {\Sigma }^{\ast },k\in \mathbb{N}:\text{simulate }\Pi (I)\text{ for }k\text{ steps and accept if line }n\text{ is reached}$$

If such an input exists, the search eventually finds it. If no input reaches line $n$, the procedure runs forever.

Why limiting $k$?

The bound $k$ is what makes the procedure semi-decidable: each simulation is forced to stop after finitely many steps. Without that limit, one simulated input could run for too long or diverge, and the search might never move on to later candidates because of the order of enumeration. The bound does not make the problem decidable; it only guarantees that a positive instance can eventually be found if one exists.

A naive unbounded enumeration would look like this:

for all input I in Σ*:
	for all k in N:
		simulate Π(I) for k steps
		if line n is reached:
			return true

The inner loop must be bounded to ensure that every candidate input is checked only for finitely many steps before the search proceeds.

Reduction from the Halting Problem

Undecidability via reduction

We reduce the halting problem to the reachable code problem.

Let $(\Pi ,I)$ be an instance of the halting problem. Choose a line label $L$ that does not occur in $\Pi$. Construct a new program ${\Pi }^{\prime }$ as follows:

Void Π'(Program Π, String I)
    Π(I);
    L: /* empty line */
    return;

Then the line with label $L$ is reachable in ${\Pi }^{\prime }$ if and only if $\Pi$ halts on input $I$.

• If $\Pi$ halts on $I$, then execution continues to line $L$.
• If $\Pi$ does not halt on $I$, then line $L$ is never reached.

Therefore, a decider for the reachable code problem would decide the halting problem. Since the halting problem is undecidable, the reachable code problem is also undecidable.