Ein Algorithmus terminiert, wenn er für jede zulässige Eingabe nach endlich vielen Schritten anhält.
Beweise nutzen oft eine Variante: eine nichtnegative Größe, die in jedem Schritt strikt kleiner wird.