检测程序是否处于无限循环（阅读：解决停止问题）

Question

检测确定性程序（即状态机）是否处于无限循环相当于解决停止问题？

我想出了一个解决方案，但我不确定为什么它不起作用：

• 让程序运行
• 当你认为它处于无限循环时，定期拍摄它的内存快照
• 如果您检测到相同的快照，则程序处于无限循环中
• 只要您没有两次获得相同的快照，要么（1）不处于无限循环中，要么（2）您需要更快地拍摄快照（也许每次内存访问都拍摄一次？）

我假设这不起作用......但为什么？

这似乎是一种完全合理的方法来检测程序是否处于无限循环中（例如，特别是如果您存储哈希值而不是内存本身，尽管这不会 100% 准确）...它有什么问题，如果有的话？

Answer 1

理论上，它不等价于停机问题，因为真实的计算机具有有限数量的可能状态（即使它很大）。停机问题所适用的图灵机具有无限存储空间。

但是，让我们进一步探讨你的想法。 您还必须拍摄“隐藏”状态的快照：CPU 的程序计数器和其他寄存器，并且您必须在每条指令之前拍摄快照。 （如果内存快照相同并且即将执行相同的指令，则程序将处于无限循环中。如果内存内容相同，但将执行除上一条指令之外的其他指令，则程序将处于无限循环中你看到同一张快照的时间。）

在实践中，即使是非常小的计算机也具有大量的潜在状态，以至于您永远无法存储（甚至是哈希值！）所有快照。 例如，即使像古老的 Commodore 64 这样具有 64kB RAM 的小型计算机也有 256^65536 个潜在状态（不包括 5 个 CPU 寄存器）。 跟踪可能如此长的周期在时间和空间上都是绝对不可行的。

Answer 2

该解决方案即使在原则上也行不通。图灵机不必处于完全相同的状态（磁带处于相同的配置）才能进入无限循环。

您的算法可能适用于上下文相关语言和线性有界自动机，但如果您不知道 TM 需要多少磁带，您将永远不知道您是否有无限循环或即将达到极限顶部。请注意，由于多种原因，您的方法显然适用于真实的计算机......其中最主要的是您的计算机不如（大）有限自动机强大。

Answer 3

我就我自己关于停机问题的想法联系了理论计算领域最优秀的专家之一，他允许我引用他的观点。

MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022
  If simulating halt decider H correctly simulates its input D 
  until H correctly determines that its simulated D would never 
  stop running unless aborted then 

  H can abort its simulation of D and correctly report that D 
  specifies a non-halting sequence of configurations. 
MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022

typedef void (*ptr)(); 
typedef int (*ptr2)(); 
int H0(ptr P); 
int H(ptr2 P, ptr2 I); 

void Infinite_Loop() 
{
  HERE: goto HERE;
}

void Infinite_Recursion()
{
  Infinite_Recursion(); 
}

void DDD() 
{
  H0(DDD); 
} 

int P(ptr2 x) 
{
  int Halt_Status = H(x, x); 
  if (Halt_Status)   
    HERE: goto HERE; 
  return Halt_Status; 
} 

int main() 
{ 
  H0(Infinite_Loop); 
  H0(Infinite_Recursion); 
  H0(DDD); 
  H(P,P); 
}

每个了解 x86 模拟器的 C 程序员都知道，当 H0 模拟 Infinite_Loop、Infinite_Recursion 和 DDD 机器语言时，它必须中止这些模拟，以便自身能够正常终止。

当这被解释为非暂停标准时，则模拟终止分析器 H0 是正确的，可以通过将 0 返回给其调用者来拒绝这些输入作为非暂停。

事实证明，同样的推理同样适用于 H(P,P)。正确模拟的对 H(P,P) 的调用不可能返回到 H 正确模拟的 P。

直接执行的 P(P) 不会出现同样的问题，因为直接执行的 P(P) 本质上是递归链中的第一个调用，而第二个调用总是被中止。

如果 H(P,P) 没有正确认识到它必须中止其输入的模拟以正确防止其自身的非终止，则直接执行的 P(P) 将永远不会停止。