-1

已知存在可判定问题、半可判定问题和不可判定问题。TM（图灵机）接受的语言是一个 re set（递归可枚举），并且在某些情况下也是一个递归集。re（但不是递归）集合的一个例子是接受某个（固定）字符串“x”的 TM 集合。解释是这样的：“这个问题是半可判定的（即集合是 re），因为如果某个 TM_i（i 是它在哥德尔枚举中的索引）属于集合，那么通过算法（过程， TM, ecc.) 列出所有接受“x”的 TM，并继续这样做，在某个点我将能够找到 TM_i。但是，如果 TM_i 不属于该集合，那么我无法得出任何结论：列出所有接受“x”的 TM 的算法将永远持续下去。

现在我试着从不同的角度思考同样的问题。假设我有一个随机图灵机 TM_j，我想确定它是否属于上述集合。我可以将字符串“x”作为输入给 TM_j，如果它在“接受”状态（最终状态）停止，那么我知道 TM_j 接受“x”，因此是集合的一部分。另一方面，如果 TM_j 不接受“x”，它可能会停止在某个非最终状态（因此我知道 TM_j 拒绝“x”），或者它可能会永远循环下去。在第二种情况下，我不能通过观察两个相同的配置来列出 TM 在执行期间的所有配置并得出结论它永远循环（因此拒绝“x”）吗？如果“c1, c2, c3, c4, . . . , c21, c3, . . 。” 是 TM_j 的配置列表，我观察到 c3 是重复的，并且由于机器是确定性的，c3 后面会跟着 c4，c4 依次给出 c5，依此类推，直到 c21，然后又是 c3。. . 因此，我可以得出结论，TM_j 循环，因此“x”不能被它接受，因为它永远不会达到最终（接受）状态。然而，这意味着给定一个通用的 TM，我可以确定它是否属于该集合，因此该集合是递归的而不是递归可枚举的！

有人可以帮助我了解我的错误在哪里吗？

4

1 回答 1

1

错误是假设永久循环的 TM 将具有重复的配置（其磁带 + 其当前状态）。

您是正确的，如果确定性图灵机两次达到特定配置，它将永远循环。

考虑机器A：

Write 0 to the output tape.
While the input tape is 'x':
  Increment the output tape in binary
Otherwise reject

这台机器永远不会在输入时停止'x'，但也永远不会重复配置（它的状态会重复，但它的磁带永远不会）。

而且，如果您认为仅凭状态就足以确定机器是否永远循环，请考虑B：

Write 0 to the output tape.
While the input tape is 'x' and the output tape is less than some specific but arbitrarily large number k:
  Increment the output take in binary
If the input tape is 'x', accept
Otherwise reject

这台机器将重复其状态任意次数，最后停止并接受'x'。

于 2020-06-23T21:16:33.157 回答