Termination analysis

In computer science, a termination analysis is program analysis which attempts to determine whether the evaluation of a given computer program will definitely terminate.

Description

Because the halting problem is undecidable, termination analysis cannot be total.

The aim is to find the answer "program does terminate" (or "program does not terminate") whenever this is possible. Without success the algorithm (or human) working on the termination analysis may answer with "maybe" or continue working infinitely long.

See also

• Complexity analysis — the problem of estimating the time needed to terminate
• Halting problem
• Loop variant
• Program analysis
• Total functional programming — a programming paradigm that restricts the range of programs to those that are provably terminating
• Undecidable problem
• Walther recursion

External links

• Termination analysis @ Wikipedia