我们可以找到一个图灵的机器，使得没有图定机器可以决定它是否停止在$ \ epsilon $？

Question

停止问题表示，没有图定机器可以确定任意图定型机是否停止在 $ \ epsilon $ 上。但我试着问一些不同的东西，我们可以找到一个特定的图灵机 $ m $ ，使得 $ l_m={0^ n：m $ 停止 $ \ epsilon \} $ 是不可判定的？ 或者至少可以证明存在如此 $ m $ ？

语言本身不是问题，它是 $ l={0 ^ n：n \ in \ mathbb {n} \} $ 或 $ l=phi $ 区分案例的方式仅在 $ l $的定义的右侧。

换句话说，我们可以定义一个图灵的机器，使我们（或图灵机）无法确定它是否停止或不在 $ \ epsilon $ 上？

Answer 1

假设您有这样的tm，即机器 $ m $ 其中问题是“ $ m $在空输入上停止？“当然，这个问题将是可判定的：两个算法中的一个必须是正确的，（1）答案“是”或（2）答案“否”。我们可能不知道哪一个是正确算法的事实在这里是无关紧要的;重要的是，我们确定的算法一个是正确的，所以我们知道问题是可判定的。更一般而言，具有有限数量的实例的任何决策问题是可解除的。