language-agnostic - 对于内存有限的计算机来说，停止真的无法确定吗？

Question

图灵证明了停机问题在图灵机上是不可判定的。然而，真正的计算机实际上并不是图灵完备的：如果它们有无限量的内存，它们就会是图灵完备的。

考虑到计算机的内存量是有限的，因此不是完全转动的，停机问题是否可以判定？我的直觉告诉我，是的，但是解决这个受限停机问题的程序可能具有与目标计算机内存大小成指数关系的时间和空间复杂度。

Answer 1

具有有限带的图灵机可以通过带无限带的图灵机来解决停机问题。无限图灵机所要做的就是枚举有限图灵机的每一个可能状态（并且可能的状态数量有限，尽管非常多），并标记图灵机在运行过程中访问过哪些状态运行程序。最终，会发生以下两种情况之一：

1. 有限图灵机将停止。
2. 有限图灵机将重新访问一个状态。如果它重新访问一个状态，那么您知道存在无限循环，因为机器是确定性的，因此下一个状态完全由前一个状态决定。如果存在n状态，则保证机器在n+1第 th 步重新访问其中之一。