所以我正在查看我的笔记以解决这个问题，我似乎无法理解这个问题是如何工作的。假设我们有 M，并且 M 接受一个使其访问每个非停止状态的输入。
我说服自己这个问题是可以判定的，但我很难证明这一点。我的答案的粗略概述是：假设我们有一个只有一个停止状态的 TM T，如果它想要通过所有状态，它需要通过这个停止状态，我们需要以某种方式显示它们如何循环通过所有的州都是这样。
任何帮助都会有所帮助，谢谢！
user4077377
问问题
1072 次
1 回答
0
我想你会发现答案实际上是无法确定的。为什么？那么这可以让你解决停机问题。
对于您描述的问题，您将获得一个 TM M 和一个输入 x 和一个 oracle Q。我们可以使用 oracle Q 解决输入 x 的 M 的停止问题吗？
首先，我们将一个新的 TM N 连接到 M 的前面。这是 N 的作用： - 删除磁带内容 - 将 x 写入磁带
M 在 x 上停止，当且仅当 NM 在所有输入上停止。这应该很容易看出，因为 N 离开磁带的方式与 M 在输入为 x 时所看到的完全一样。我们可以设计 N 使得 N 的所有状态都被访问。
现在，通过添加第二个磁带将 M 修改为 M'。第二个磁带将用于跟踪我们访问过的 M' 的最高编号状态。将转换添加到 M'，它从辅助磁带读取第 n 个状态并导致 M' 转换到 (n+1)st 状态。从 M' 的最高编号状态的转换应该返回到 M' 的初始状态，并在辅助磁带上写入类似“已完成”的内容。当 M' 在辅助磁带上看到“完成”时，它的行为就像 M 所做的那样，并且只考虑主磁带。
所以 M' 和 M' 完全一样，除了它首先访问 M 的所有状态，然后重置，之后它的行为就像 M 一样。
M' 在 x 上停止当且仅当 M 在 x 上停止。如果 M 在 x 上停止，NM' 也会停止。
最后，我们准备好证明了。如果 M 在 x 处停止，则预言机 Q 接受 NM'。如果 NM' 接受导致 NM' 访问所有状态的输入 y，Q 接受 NM'。但是： - 所有输入 y 导致 NM' 访问所有状态（因为 N 的所有状态都通过构造来访问，并且 M' 的所有状态都通过修改 M 来访问）；所以 Q 真的只是在回答“NM' 接受任何字符串吗？”这个问题。- NM' 从输入磁带中擦除 y，写入 x 并将其交给 M'。所以输入 y 无关紧要；如果 NM' 接受任何输入，它会接受所有输入。如果 M' 接受 x，它会接受所有这些。- M' 接受与 M 相同的语言。
所以应用于 NM' 的 Q 确实告诉我们 M 是否在 x 处停止。然后 Q 解决了停机问题。
于 2016-06-23T18:00:30.900 回答