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

Question

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

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

Answer 1

具有有限 strip 的图灵机可以通过具有无限 strip 的图灵机解决停机问题。无限图灵机所要做的就是枚举有限图灵机的每个可能状态(并且将有一个有限但非常多的可能状态)并标记图灵机在此过程中访问了哪些状态运行一个程序。最终，将发生以下两种情况之一:

有限图灵机将停止。

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