termination analysis

A program analysis which attempts to determine whether

evaluation of a given expression will definitely terminate.

Evaluation of a constant is bound to terminate, as is

evaluation of a non-recursive function applied to arguments

which are either not evaluated or which can themselves be

proved to terminate. A recursive function can be shown to

terminate if it can be shown that the arguments of the

recursive calls are bound to reach some value at which the

recursion will cease.

Termination analysis can never guarantee to give the correct

answer because this would be equivalent to solving the

halting problem so the answer it gives is either "definitely

terminates" or "don't know".

(1994-10-20)