如何检查程序是否终止？
是否有一个通用规则可以用来确定这一点？例如：
int i = 10;
while (i > 1 ) {
if (i%2 == 0) i = i/2;
else i = 3*i - 1;
}
Is there a general rule that can be used to determine this? E.g:
int i = 10;
while (i > 1 ) {
if (i%2 == 0) i = i/2;
else i = 3*i - 1;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这是停止问题。不存在能够满足您要求的算法。
特别是，如果存在这样的算法，那么 collatz 猜想，与您的函数相关问题，将是微不足道的（或者至少容易得多）。
This is the halting problem. There does not exist an algorithm capable of doing what you ask.
In particular, if there was such an algorithm, then the collatz conjecture, related to the function in your question, would be trivial (or at least a lot easier).
您可能指的是停止问题。简而言之，没有通用的方法来确定程序是否会停止。查看这篇文章。
You may be referring to the stopping problem. In short, there is no general way to determine if a program will stop. Check out this article.
一般来说，“不”。正如其他人所说，通过您的具体示例，可以证明它不会终止，因为如果
i为偶数（或者如果i是非正且奇怪的，但考虑到初始条件，这永远不会发生）。最小的正偶数是 2，在下一次迭代中它将变为 1，然后将变为 2。有趣的是，您没有检查 Collatz 猜想，因为您正在迭代“如果偶数则减半，3*”如果是奇数，则为 n-1”，并且 Collatz 猜想会迭代“如果是偶数，则减半，如果是奇数，则为 3*n+1”。我无法通过快速搜索找到讨论的这个序列。
In general, "no". As everyone else have said, with your specific example, it can be proven not to terminate, as
iis only ever smaller ifiis even (or ifiis non-positive and odd, but given the initial conditions, that will never happen). The smallest positive even number is 2, this will then turn to 1 for the next iteration, where it will then be turned into 2.Interestingly, you're not checking the Collatz Conjecture, as you are iterating "halve if even, 3*n-1 if odd" and the Collatz Conjecture iterates "halve if even, 3*n+1 if odd". I can't find this sequence discussed with a quick search.
终止分析有多种方法
可以证明程序是否会停止。这在图灵完备的编程语言中并不总是可行，但有几种全函数式编程语言仅限于可证明停止的程序。
There are several methods for termination analysis
that can prove whether a program will halt. This is not always possible in Turing-complete programming languages, but there are several total functional programming languages that are limited to provably-halting programs.