證明程式正確——迴圈不變量、歸納法與停機性
不變量的維持(maintenance)
維持是迴圈證明的核心:它證明走過一次迴圈本體仍保住不變量為真。你假設不變量在某一輪的開頭成立(這個假設就是歸納假設),追蹤本體做了什麼,再驗證不變量在下一輪開頭再次成立。回到梯子:假設你現在這一階托盤是平的,你要檢查你跨一步的方式能讓下一階托盤仍然平。
要小心的地方是:你只能假設「當前這一輪」的不變量,而不能假設你期望的最終答案。你逐步走過本體對變數的影響,再用更新後的值重新建立不變量。以插入排序為例,假設「A[1..i-1] 已排序」;本體把 A[i] 往左滑過比它大的元素並放到正確位置,之後「A[1..i] 已排序」,而由於 i 接著變成 i+1,不變量「A[1..i-1] 已排序」便再次成立。注意不變量是針對新的 i 重新陳述的。整個論證只談一輪;你從不直接對「所有輪次一次」推理——那件事由歸納法替你完成。
維持是幾乎所有真實錯誤現形的地方,因為它逼你正面處理本體的每一行與資料的每一個邊界。如果你證不出維持,那不是本體有錯,就是你的不變量太強(宣稱的比本體能保住的多)或太弱(沒帶足夠資訊往前傳)。它與初始化(基底情形)配對,藉由歸納法得出:不變量在每一輪之前都成立。
累加和,不變量「s = A[1..i-1] 之和」。在第 i 輪假設它成立。本體做 s = s + A[i];i = i + 1。執行後「s + A[i]」等於「A[1..i] 之和」,而當 i 變成 i+1 後,這正好是「A[1..(新 i)-1] 之和」。不變量重新建立。
假設不變量,執行本體,再對更新後的變數證明它再次成立。
常見陷阱:在維持步驟中,你只能把「當前這一輪」的不變量當作假設——若把你想證明的後續輪次結論拿來當前提,那就是循環論證、無效。
又稱
另見