1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven May 27 at 14:42
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.