图灵机和可判定性
Turing machines and decidability
已知有可判定问题、半可判定问题和不可判定问题。 TM（图灵机）接受的语言是r.e。集合（递归可枚举），在某些情况下，也是递归集合。一个集合的例子是 r.e。 （但不是递归的）是接受某个（固定的）字符串“x”的 TM 集合。解释是这样的：“这个问题是半可判定的（即集合是r.e。）因为如果某个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，它依次给出 c5，依此类推直到 c21，然后是 c3再次。 . .因此我可以得出结论，TM_j 循环因此“x”不能被它接受，因为它永远不会达到最终（接受）状态。然而，这意味着给定一个通用 TM 我可以确定它是否属于集合，因此集合是递归的而不是递归可枚举的！
有人可以帮助我了解我的错误所在吗？
错误是假设永远循环的 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'。
已知有可判定问题、半可判定问题和不可判定问题。 TM（图灵机）接受的语言是r.e。集合（递归可枚举），在某些情况下，也是递归集合。一个集合的例子是 r.e。 （但不是递归的）是接受某个（固定的）字符串“x”的 TM 集合。解释是这样的：“这个问题是半可判定的（即集合是r.e。）因为如果某个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，它依次给出 c5，依此类推直到 c21，然后是 c3再次。 . .因此我可以得出结论，TM_j 循环因此“x”不能被它接受，因为它永远不会达到最终（接受）状态。然而，这意味着给定一个通用 TM 我可以确定它是否属于集合，因此集合是递归的而不是递归可枚举的！
有人可以帮助我了解我的错误所在吗？
错误是假设永远循环的 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'。