正在检测程序（即状态机）是否处于无限循环等同于解决暂停问题的确定性程序？检测程序是否处于无限循环（阅读：解决暂停问题）
我想出了一个解决方案，我不知道为什么它不应该工作：
我假设这不起作用......但为什么？
这似乎是一个非常合理的方式来检测程序是否处于无限循环（例如，特别是如果您存储散列而不是内存本身，但这不会100％准确）......它有什么问题， 如果有什么？
该解决方案即使原则上也不起作用。图灵机不必处于完全相同的状态（磁带处于相同配置）进入无限循环。
你的算法可能适用于上下文敏感语言和线性有界自动机，但是如果你不知道TM需要多少磁带，你永远不会知道你是否有无限循环或者击中顶端。请注意，由于各种原因，您的方法显然适用于真正的计算机......其中最主要的是您的计算机不如（大）有限自动机强大。
从理论上讲，它是不相当于停机问题，因为真正的计算机有可能状态的数量有限（即使它是巨大的）。停机问题适用的图灵机具有无限存储。
但是，让我们进一步探索您的想法。您还必须拍摄“隐藏”状态的快照：CPU的程序计数器和其他寄存器，并且您必须在每条指令之前拍摄快照。 （如果内存快照是相同的，并且即将执行相同的指令，则该程序将处于无限循环中。如果内存内容相同，但其他内容将会比上一次执行的内容无效当你看到相同的快照时）。
实际上，即使是一台非常小的计算机也拥有如此巨大数量的潜在状态，您永远无法存储（甚至不会散列！）所有快照。例如，即使是像64kB RAM的古代商品64那样的小型计算机也有256^65536个潜在状态（不包括5个CPU寄存器）。跟踪周期可能很长，在时间和空间上都是绝对不可行的。
@Downvoter：小心点评？ – Mehrdad
几分钟前，我想到了这个想法，我很高兴别人已经提出并关心问。谢谢。 –
我在看到你之前打开了一个类似的问题：http://stackoverflow.com/q/16250472/1858225（请注意，我的问题也是基于另一个我认为过早关闭的问题。）我认为，而不是将我的标记为重复我只是在这里留下这个评论，因为我的问题是更具体一点，我的答案区分这和停止问题。 –