在半可判定的较少线达到较少？

Question

假设我们有两个程序 $ p_1 $ 和 $ p_2 $ 和两个行号 $ n_1 $ 和 $ n_2 $ 。 $ p_1 $ 到达 $ n_1 $ 比 $ p_2 $ 到达 $ n_2 $ ？通过减少停止，这显然不是可判定的，但我认为它是半可判定的。

要执行此操作，我会构建一个解释器，执行 $ p_1 $ 和 $ p_2 $ 同时逐步逐步，计算每个程序的步骤。一旦 $ p_1 $ 到达 $ n_1 $ ，我将步骤数与 $ N_2 $ ，如果较少，则返回true。如果 $ p_2 $ 到达 $ n_2 $ 首先，我返回false。如果没有程序到达 $ n_1 $ 或 $ n_2 $ ，则不会发生任何事情（半解密性之后）。

Answer 1

如果您非常仔细地使用决策问题，它只是半删除。并且您必须以这样的方式单词，即两个程序永远不会到达它们的 $ n $ s处于拒绝类别中。由于<跨度类=“math-container”> $ \ infty 是模糊/未定义的，我会在决策问题中明确提及这种情况。

除此之外，是的，它是正确的。如果 $ p_1 $ 或 $ p_2 $ 停止（查看 $ N $ 只是另一个暂停条件）并在这种情况下提供正确的答案。如果修补上述问题，那么既不是 $ p_1，p_2 $ 停止您在拒绝案例中，因此允许您的半解密性也永远不会停止。