# Is reaching in less lines semi-decidable?

Assuming we have two programs $$p_1$$ and $$p_2$$ and two line numbers $$n_1$$ and $$n_2$$. Does $$p_1$$ reach $$n_1$$ in less computational steps than $$p_2$$ reaches $$n_2$$? By reduction from Halting, this is clearly not decidable, but I think it is semi decidable.

To do so, I would build an interpreter, that executes $$p_1$$ and $$p_2$$ simultaneously step by step and count the steps for each program. As soon as $$p_1$$ reaches $$n_1$$, I compare the number of steps to $$n_2$$ and return true if it is less. If $$p_2$$ reaches $$n_2$$ first, I return false. In case no program reaches $$n_1$$ or $$n_2$$, nothing happens (following semi-decidability).

• Your argument seems correct. Although I think that this kind of "is my answer correct?" questions are discouraged since only yes/no answers are possible. May 27, 2020 at 14:42

It's only semi-decidable if you word your decision problem very carefully. And you have to word it in such a way that the case where both programs never reach their $$n$$s is in the REJECT category. Since $$\infty < \infty$$ is ambiguous/undefined I would explicitly mention this case in your decision problem.
Other than that, yes it's correct. Your machine halts if either $$p_1$$ or $$p_2$$ halts (viewing reaching $$n$$ as just another halting condition) and provides the correct answer in such a scenario. If you patch up the above issue then when neither $$p_1, p_2$$ halts you are in the REJECT case and thus you are allowed to never halt as well by semi-decidability.