图灵机和可判定性

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'