# Termination analysis

## From Wikipedia, the free encyclopedia

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.

```
void f(int n) {
while (n > 1)
if (n % 2 == 0)
n = n / 2;
else
n = 3 * n + 1;
}
``` |

As of 2024^{[update]}, it is still unknownwhether this C-program terminates for every input; see Collatz conjecture. |

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 $\Pi _{2}^{0}$ 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.