Exactly One of Two Reachable Code Problem

computation

Definition

Exactly One of Two Reachable Code Problem

The exactly one of two reachable code problem is a decision problem that asks, for a given program $\Pi$, two input strings $I_1,I_2$, and a label $L$, whether the code with label $L$ is executed for exactly one of the two inputs.

Instance: program $\Pi$, strings $I_1,I_2$, label $L$
Question: Does $\Pi$ execute the line with label $L$ on exactly one of the inputs $I_1$ and $I_2$?

Reduction from the Co-Halting Problem

Non-semi-decidability via reduction

We reduce the co-halting problem with non-empty input strings to the exactly one of two reachable code problem.

Let $(\Pi ,I)$ be an instance of the co-halting problem with $I\ne ϵ$. Construct a new program ${\Pi }^{\prime }$ and choose a label $L$ that does not occur in $\Pi$:

Void Π'(Program Π, String I)
if (I ≠ ε) {
    call Π(I);
}
L: /* no-op */
return;

Set

$$I_1:=ϵ,I_2:=I.$$

Then:

• on input $I_1$, the condition $I\ne ϵ$ is false, so ${\Pi }^{\prime }$ reaches $L$;
• on input $I_2$, the program executes $\Pi (I)$ first, so $L$ is reached if and only if $\Pi$ halts on $I$.

Hence, $L$ is reached for exactly one of the two inputs $I_1$ and $I_2$ if and only if $\Pi$ does not halt on $I$.

Therefore, a recogniser for the exactly one of two reachable code problem would recognise the co-halting problem with non-empty inputs. Since the co-halting problem with non-empty inputs is not semi-decidable, the exactly one of two reachable code problem is not semi-decidable.

Complement Relation

Co-problem transfer

Based on the reduction above, for any two decision problems $P_1$ and $P_2$, the following equivalence holds:

$$P_1\le P_2⟺\mathrm{co}(P_1)\le \mathrm{co}(P_2).$$

Thus, from the reduction

$$\text{Halting Problem-NLS}\le \text{Exactly One of Two Reachable Code Problem}$$

one can use the following construction:

Void Π'(Program Π, String I)
if (I = ε) {
    return;
}
call Π(I);
L: /* no-op */
return;

Set

$$I_1:=ϵ,I_2:=I.$$

Then the label $L$ is reached on $I_1$ only if the input is non-empty, and it is reached on $I_2$ if and only if $\Pi$ halts on $I$.

Therefore,

$$\text{co-Halting Problem-NLS}\le \text{co-Exactly One of Two Reachable Code Problem}.$$

Since the co-halting problem with non-empty inputs is not semi-decidable, the co-exactly one of two reachable code problem is not semi-decidable.