終止性（termination）

終止性意味著演算法總會停下——對每一個合法輸入，它都在有限步之後抵達終點，而不是永遠空轉。這是演算法定義本身的一部分：一份永不結束的食譜，是你無法使用的食譜。一台跑無限漂洗循環的洗衣機，不論把衣服洗得多乾淨都算壞了；一個永不回傳答案的演算法也有同樣的毛病，不論那答案本來會多正確。

保證終止性的常見辦法，是找出一個嚴格遞減、且不可低於某個下限的量。每繞一次迴圈都必須讓這個量變小，既然它不能永遠下降，迴圈就必須結束。看看歐幾里得求最大公因數的方法：gcd(a, b) 反覆把 (a, b) 換成 (b, a mod b)。第二個數是一個非負整數，每步都嚴格縮小（a mod b 永遠小於 b），而一個嚴格遞減的非負整數序列不可能永遠繼續，所以這個過程必定抵達 b = 0 而停下。這單一的觀察——一個總在遞減的非負整數——正是你會遇到的幾乎每個終止性論證的核心。

終止性與正確性確實是兩回事，而你兩者都需要。一個演算法可能在它真的結束時都給對答案、卻仍在某些輸入上卡住（有部分正確性而無終止性），這在實務上毫無用處。這裡還有一道深刻的界限：並不存在一個通用程序，能看著任意程式就判定它對某給定輸入是否停機——這就是著名的停機問題，已被證明無法解決。所以一般而言我們無法把終止性檢查自動化；我們得一個案例一個案例地手動論證，通常靠一個遞減的量。