检测确定性程序（即状态机）是否处于等效于解决停机问题的无限循环中？
我想出了一个解决方案，但我不确定为什么它不应该工作：
我假设这不起作用……但是为什么呢？
这似乎是检测程序是否处于无限循环中的一种完全合理的方法（例如，特别是如果您存储哈希而不是内存本身，尽管这不会 100% 准确）......它有什么问题，如果有的话？
从理论上讲，它不等同于停机问题，因为真正的计算机具有有限数量的可能状态（即使它很大）。适用于停机问题的图灵机具有无限的存储空间。
但是，让我们进一步探索您的想法。您还必须拍摄“隐藏”状态的快照：CPU 的程序计数器和其他寄存器，并且必须在每条指令之前拍摄快照。（如果内存快照相同并且即将执行相同的指令，则程序将处于无限循环中。如果内存内容相同，则无济于事，但是将执行除上一个之外的其他内容您看到相同快照的时间。）
在实践中，即使是非常小的计算机也有如此大量的潜在状态，以至于您永远无法存储（甚至哈希！）所有快照。例如，即使是像古代 commodore 64 这样具有 64kB RAM 的小型机也有 256^65536 个潜在状态（不包括 5 个 CPU 寄存器）。可能如此长的跟踪周期在时间和空间上都是绝对不可行的。
该解决方案即使在原则上也行不通。图灵机不必处于完全相同的状态（磁带具有相同的配置）即可进入无限循环。
您的算法可能适用于上下文相关语言和线性有界自动机，但如果您不知道 TM 需要多少磁带，您将永远不知道您是否有无限循环或即将达到顶峰. 请注意，由于多种原因，您的方法显然适用于真正的计算机……其中主要是您的计算机不如（大）有限自动机强大。