algorithm - 如何检查程序是否终止？

Question

是否有可用于确定这一点的一般规则？例如：

int i = 10;
while (i > 1 ) {
  if (i%2 == 0) i = i/2;
  else i = 3*i - 1;
}

Answer 1

这就是停机问题。不存在能够满足您要求的算法。

特别是，如果有这样的算法，那么与您问题中的函数相关的collat​​z 猜想将是微不足道的（或者至少容易得多）。

Answer 2

您可能指的是停止问题。简而言之，没有通用的方法来确定程序是否会停止。看看这篇文章。

Answer 3

一般来说，“不”。正如其他人所说，通过您的具体示例，可以证明它不会终止，因为i如果i是偶数（或者如果i是非正数和奇数，但考虑到初始条件，那将永远不会发生）。最小的正偶数是 2，这将在下一次迭代中变为 1，然后将变为 2。

有趣的是，您没有检查 Collat​​z 猜想，因为您正在迭代“偶数减半，奇数 3*n-1”，而 Collat​​z 猜想迭代“偶数减半，奇数 3*n+1”。我找不到通过快速搜索讨论的这个序列。

Answer 4

有几种终止分析 方法可以证明程序是否会停止。这在图灵完备的编程语言中并不总是可能的，但是有几种完全的函数式编程语言仅限于可证明的停止程序。