How do I check if a program terminates?

Question

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;
}

Answer 1

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).

Answer 2

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.

Answer 3

In general, "no". As everyone else have said, with your specific example, it can be proven not to terminate, as i is only ever smaller if i is even (or if i is 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.

Answer 4

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.