Termination analysis

def f(n):
   while n > 1:
      if n % 2 == 0:
          n = n / 2
      else:
          n = 3 * n + 1
As of 2024, it is still unknown
whether this Python program
terminates for every input;
see Collatz conjecture.

In computer science, termination analysis is program analysis which attempts to determine whether the evaluation of a given program halts for each input. This means to determine whether the input program computes a total function.

It is closely related to the halting problem, which is to determine whether a given program halts for a given input and which is undecidable. The termination analysis is even more difficult than the Halting problem: the termination analysis in the model of Turing machines as the model of programs implementing computable functions would have the goal of deciding whether a given Turing machine is a total Turing machine, and this problem is at level of the arithmetical hierarchy and thus is strictly more difficult than the Halting problem.

Now as the question whether a computable function is total is not semi-decidable,[1] each sound termination analyzer (i.e. an affirmative answer is never given for a non-terminating program) is incomplete, i.e. must fail in determining termination for infinitely many terminating programs, either by running forever or halting with an indefinite answer.

  1. ^ Rogers, Jr., Hartley (1988). Theory of recursive functions and effective computability. Cambridge (MA), London (England): The MIT Press. p. 476. ISBN 0-262-68052-1.