证明这种语言是可判定的还是不可判定的
Prove whether this language is decidable or undecidable
所以我正在复习我关于这个问题的笔记，但我似乎无法理解这个问题是如何发生的。假设我们有 M，M 接受一个输入，使其访问每个非停止状态。
我说服自己这个问题是可判定的，但我很难证明这一点。我的答案的粗略概述是：假设我们有一个只有一个停止状态的 TM T，如果它想经历所有状态，它需要通过这个停止状态，我们需要以某种方式展示它们如何循环所有州都是如此。
任何帮助都是有益的，谢谢！
我想你会发现答案实际上是不可判定的。为什么？那么这将让你解决停机问题。
针对您描述的问题，您将获得一个 TM M 和一个输入 x 以及一个 oracle Q。我们可以使用 oracle Q 解决输入 x 的 M 的停机问题吗？
首先，我们将一个新的TM N连接到M的前面。这是N的作用：
- 删除磁带内容
- 将 x 写入磁带
M 在 x 上停止当且仅当 NM 在所有输入上停止。这应该很容易看出，因为如果输入是 x，N 离开磁带与 M 看到的完全一样。我们可以这样设计N，使得N的所有状态都被访问。
现在，通过添加第二个磁带将 M 修改为 M'。第二盘磁带将用于跟踪我们访问过的 M' 的最高编号状态。向 M' 添加转换，它从辅助磁带读取第 n 个状态并导致 M' 转换到第 (n+1) 个状态。从 M' 的最高编号状态的过渡应该 return 到 M' 的初始状态，并在辅助磁带上写下类似 "finished" 的内容。当 M' 在辅助磁带上看到 "finished" 时，它的行为与 M 一样，只考虑主磁带。
所以 M' 做的和 M' 做的完全一样，除了它首先访问 M 的所有状态然后重置，然后它的行为就像 M 一样。
M' 在 x 上停止当且仅当 M 在 x 上停止。 NM' 也停止当且仅当 M 在 x 上停止。
我们终于准备好证明了。预言机 Q 接受 NM' 当且仅当 M 在 x 上停止。如果 NM' 接受导致 NM' 访问所有状态的输入 y，则 Q 接受 NM'。但：
- 所有输入 y 都会导致 NM' 访问所有状态（因为 N 的所有状态都通过构造访问，而 M' 的所有状态都通过修改 M 访问）；所以 Q 实际上只是在回答问题 "does NM' accept any strings?"
- NM' 从输入磁带中擦除 y，写入 x 并将其交给 M'。所以输入 y 并不重要；如果 NM' 接受任何输入，它会接受所有输入。如果 M' 接受 x，它就会接受所有这些。
- M' 接受与 M 相同的语言。
所以 Q 应用于 NM' 确实告诉我们 M 是否在 x 上停止。然后Q解决了停机问题。
所以我正在复习我关于这个问题的笔记，但我似乎无法理解这个问题是如何发生的。假设我们有 M，M 接受一个输入，使其访问每个非停止状态。
我说服自己这个问题是可判定的，但我很难证明这一点。我的答案的粗略概述是：假设我们有一个只有一个停止状态的 TM T，如果它想经历所有状态，它需要通过这个停止状态，我们需要以某种方式展示它们如何循环所有州都是如此。
任何帮助都是有益的，谢谢！
我想你会发现答案实际上是不可判定的。为什么？那么这将让你解决停机问题。
针对您描述的问题，您将获得一个 TM M 和一个输入 x 以及一个 oracle Q。我们可以使用 oracle Q 解决输入 x 的 M 的停机问题吗？
首先，我们将一个新的TM N连接到M的前面。这是N的作用： - 删除磁带内容 - 将 x 写入磁带
M 在 x 上停止当且仅当 NM 在所有输入上停止。这应该很容易看出，因为如果输入是 x，N 离开磁带与 M 看到的完全一样。我们可以这样设计N，使得N的所有状态都被访问。
现在，通过添加第二个磁带将 M 修改为 M'。第二盘磁带将用于跟踪我们访问过的 M' 的最高编号状态。向 M' 添加转换，它从辅助磁带读取第 n 个状态并导致 M' 转换到第 (n+1) 个状态。从 M' 的最高编号状态的过渡应该 return 到 M' 的初始状态，并在辅助磁带上写下类似 "finished" 的内容。当 M' 在辅助磁带上看到 "finished" 时，它的行为与 M 一样，只考虑主磁带。
所以 M' 做的和 M' 做的完全一样，除了它首先访问 M 的所有状态然后重置，然后它的行为就像 M 一样。
M' 在 x 上停止当且仅当 M 在 x 上停止。 NM' 也停止当且仅当 M 在 x 上停止。
我们终于准备好证明了。预言机 Q 接受 NM' 当且仅当 M 在 x 上停止。如果 NM' 接受导致 NM' 访问所有状态的输入 y，则 Q 接受 NM'。但： - 所有输入 y 都会导致 NM' 访问所有状态（因为 N 的所有状态都通过构造访问，而 M' 的所有状态都通过修改 M 访问）；所以 Q 实际上只是在回答问题 "does NM' accept any strings?" - NM' 从输入磁带中擦除 y，写入 x 并将其交给 M'。所以输入 y 并不重要；如果 NM' 接受任何输入，它会接受所有输入。如果 M' 接受 x，它就会接受所有这些。 - M' 接受与 M 相同的语言。
所以 Q 应用于 NM' 确实告诉我们 M 是否在 x 上停止。然后Q解决了停机问题。