termination

Termination means the algorithm always stops — for every legal input, it reaches its end after finitely many steps rather than spinning forever. This is part of the very definition of an algorithm: a recipe that never finishes is not a recipe you can use. A washing machine that ran an infinite rinse cycle would be broken no matter how clean it got the clothes; an algorithm that never returns an answer has the same problem, however right that answer would have been.

The usual way to guarantee termination is to find a measure that strictly decreases and cannot go below some floor. Each pass through the loop must make this quantity smaller, and since it cannot drop forever, the loop must end. Consider Euclid's method for the greatest common divisor: gcd(a, b) repeatedly replaces (a, b) with (b, a mod b). The second number is a nonnegative whole number that strictly shrinks every step (a mod b is always less than b), and a strictly decreasing sequence of nonnegative integers cannot continue forever, so the process must reach b = 0 and stop. That single observation — a nonnegative integer that always decreases — is the heart of nearly every termination argument you will meet.

Termination is genuinely separate from correctness, and you need both. An algorithm can give the right answer whenever it does finish yet still hang on some inputs (partial correctness without termination), and that is useless in practice. There is also a deep limit here: there is no general procedure that can look at an arbitrary program and decide whether it halts on a given input — this is the famous halting problem, proven unsolvable. So in general we cannot automate termination checking; we argue it by hand, case by case, usually with a decreasing measure.