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

Question

假设我想找到一个自然数 n 使得 n+n=3 为了通过计算解决这个问题，我会运行一个算法：

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

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

Answer 1

在回答所提出的具体问题 ("is there an algorithm that can predict if this loop will be infinite or finite") 时，该算法将简单地报告 "INFINITE"。

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

Answer 2

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

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

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

Recognition of Undecidable Propositions(infinite loop)

halting-problem