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

Question

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

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

Answer 1

这是 halting problem .不存在能够满足您要求的算法。

特别是，如果有这样的算法，那么 collatz conjecture ，与您问题中的功能相关，将是微不足道的(或至少容易得多)。