Termination analysis

From HandWiki
void f(int n) {
   while (n > 1)
      if (n % 2 == 0)
          n = n / 2;
      else
          n = 3 * n + 1;
}
(As of 2023), it is still unknown
whether this C-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 [math]\displaystyle{ \Pi^0_2 }[/math] 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.

Termination proof

A termination proof is a type of mathematical proof that plays a critical role in formal verification because total correctness of an algorithm depends on termination.

A simple, general method for constructing termination proofs involves associating a measure with each step of an algorithm. The measure is taken from the domain of a well-founded relation, such as from the ordinal numbers. If the measure "decreases" according to the relation along every possible step of the algorithm, it must terminate, because there are no infinite descending chains with respect to a well-founded relation.

Some types of termination analysis can automatically generate or imply the existence of a termination proof.

Example

An example of a programming language construct which may or may not terminate is a loop, as they can be run repeatedly. Loops implemented using a counter variable as typically found in data processing algorithms will usually terminate, demonstrated by the pseudocode example below: 

i := 0
loop until i = SIZE_OF_DATA
    process_data(data[i])) // process the data chunk at position i
    i := i + 1 // move to the next chunk of data to be processed

If the value of SIZE_OF_DATA is non-negative, fixed and finite, the loop will eventually terminate, assuming process_data terminates too.

Some loops can be shown to always terminate or never terminate through human inspection. For example, the following loop will, in theory, never stop. However, it may halt when executed on a physical machine due to arithmetic overflow: either leading to an exception or causing the counter to wrap to a negative value and enabling the loop condition to be fulfilled. 

i := 1
loop until i = 0
    i := i + 1

In termination analysis one may also try to determine the termination behaviour of some program depending on some unknown input. The following example illustrates this problem. 

i := 1
loop until i = UNKNOWN
    i := i + 1

Here the loop condition is defined using some value UNKNOWN, where the value of UNKNOWN is not known (e.g. defined by the user's input when the program is executed). Here the termination analysis must take into account all possible values of UNKNOWN and find out that in the possible case of UNKNOWN = 0 (as in the original example) the termination cannot be shown.

There is, however, no general procedure for determining whether an expression involving looping instructions will halt, even when humans are tasked with the inspection. The theoretical reason for this is the undecidability of the Halting Problem: there cannot exist some algorithm which determines whether any given program stops after finitely many computation steps.

In practice one fails to show termination (or non-termination) because every algorithm works with a finite set of methods being able to extract relevant information out of a given program. A method might look at how variables change with respect to some loop condition (possibly showing termination for that loop), other methods might try to transform the program's calculation to some mathematical construct and work on that, possibly getting information about the termination behaviour out of some properties of this mathematical model. But because each method is only able to "see" some specific reasons for (non)termination, even through combination of such methods one cannot cover all possible reasons for (non)termination.[citation needed]

Recursive functions and loops are equivalent in expression; any expression involving loops can be written using recursion, and vice versa. Thus the termination of recursive expressions is also undecidable in general. Most recursive expressions found in common usage (i.e. not pathological) can be shown to terminate through various means, usually depending on the definition of the expression itself. As an example, the function argument in the recursive expression for the factorial function below will always decrease by 1; by the well-ordering property of natural numbers, the argument will eventually reach 1 and the recursion will terminate. 

function factorial (argument as natural number)
    if argument = 0 or argument = 1
        return 1
    otherwise
        return argument * factorial(argument - 1)

Dependent types

Termination check is very important in dependently typed programming language and theorem proving systems like Coq and Agda. These systems use Curry-Howard isomorphism between programs and proofs. Proofs over inductively defined data types were traditionally described using induction principles. However, it was found later that describing a program via a recursively defined function with pattern matching is a more natural way of proving than using induction principles directly. Unfortunately, allowing non-terminating definitions leads to logical inconsistency in type theories[citation needed], which is why Agda and Coq have termination checkers built-in.

Sized types

One of the approaches to termination checking in dependently typed programming languages are sized types. The main idea is to annotate the types over which we can recurse with size annotations and allow recursive calls only on smaller arguments. Sized types are implemented in Agda as a syntactic extension.

Current research

There are several research teams that work on new methods that can show (non)termination. Many researchers include these methods into programs[2] that try to analyze the termination behavior automatically (so without human interaction). An ongoing aspect of research is to allow the existing methods to be used to analyze termination behavior of programs written in "real world" programming languages. For declarative languages like Haskell, Mercury and Prolog, many results exist[3][4][5] (mainly because of the strong mathematical background of these languages). The research community also works on new methods to analyze termination behavior of programs written in imperative languages like C and Java.

Because of the undecidability of the Halting Problem research in this field cannot reach completeness. One can always think of new methods that find new (complicated) reasons for termination.

See also

References

  1. ↑ Rogers, Jr., Hartley (1988). Theory of recursive functions and effective computability.. Cambridge (MA), London (England): The MIT Press. pp. 476. ISBN 0-262-68052-1. 
  2. ↑ Tools at termination-portal.org
  3. ↑ Giesl, J.; Swiderski, S.; Schneider-Kamp, P.; Thiemann, R.. "Automated Termination Analysis for Haskell: From Term Rewriting to Programming Languages (invited lecture)". in Pfenning, F. (postscript). Term Rewriting and Applications, 17th Int. Conf., RTA-06. 4098. pp. 297–312. (link: springerlink.com). http://verify.rwth-aachen.de/psk/papers/RTA06Haskell.ps. 
  4. ↑ Compiler options for termination analysis in Mercury
  5. ↑ http://verify.rwth-aachen.de/giesl/papers/lopstr07-distribute.pdf[bare URL PDF]

Research papers on automated program termination analysis include:

System descriptions of automated termination analysis tools include:

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Termination_analysis&oldid=3382224"