halting-problem - 不可判定命题的识别（无限循环）

Question

假设我想找到一个 n+n=3 的自然数 n 为了计算地解决这个问题，我将运行一个算法：

int n = 1;
while(n+n!=3)
    n++;
System.out.println(n);

当然我们知道这个循环是一个无限循环。但是有没有一种算法可以预测这个循环是无限的还是有限的？（与停止机器相似但不同，因为我想要的算法只检查这个循环，而停止机器可以检查所有循环）如果有，算法是什么？

Answer 1

为了回答所提出的具体问题（“是否有一种算法可以预测这个循环是无限的还是有限的”），该算法只是简单地报告“INFINITE”。

如果您正在寻找更通用的东西（即处理任意源代码），则有一些算法可以处理各种算法/代码。但是很长一段时间以来，人们就知道一般情况下不存在这样的算法。

Answer 2

当该程序运行时，其状态可以完全由变量“n”的值和要执行的下一个操作（在有限的一组操作中）定义。算法可以逐步模拟该程序的执行，在每一步检查数据和下一个操作是否与前一步的操作相匹配。如果找到匹配项，则算法停止模拟并报告程序没有停止。如果未找到匹配项，则会记录程序的新状态以供将来比较。如果没有进一步的操作要执行，即程序自行运行完毕，则算法报告程序停止。

这个算法当然是非常低效的，但它展示了一个非常普遍的情况：可以预测特定程序是否停止，当该程序不使用任意大量内存（用于代码和数据）时。