證明正確性，而非僅僅看似合理（correctness, not plausibility）

想像你寫了一個排序程式。你拿幾筆清單跑一跑，結果看起來都對，於是宣告大功告成。但你只驗證了這幾筆輸入而已。也許它在空清單上會出錯，或在已經排好序的清單上、或在有重複值的清單上會出錯。「在我試的例子上看起來都對」只是一種看似合理的感覺，不是保證。證明正確性，意思是要證明這個演算法在每一個合法輸入上都給出正確答案，包括那些你從未試過的輸入。

這正是「證據」與「證明」的差別。測試只是在龐大的輸入空間中抽樣幾個點；就算通過了數十億筆測試，仍然有無窮多個情況未被測到。正確性證明則是用一條固定且有限的推理鏈，一次論證所有輸入。為此最主要的工具是迴圈不變量（在迴圈每一輪都保持為真的性質）與數學歸納法（藉由證明基底情形與歸納步驟，對所有規模一併證明）。典型的證明會說：先精確陳述演算法應該做什麼，再用不變量或歸納法證明它總是恰好做到那件事，最後證明它總會停下來。

這件事之所以重要，是因為看似合理的演算法經常是錯的：邊界差一的二分搜尋、在你的例子上最佳但一般情況下並非最佳的貪婪規則、在某個古怪輸入上會永遠迴圈的遞迴。測試仍然有價值，能便宜地抓出真實錯誤，但它只能顯示錯誤存在，永遠無法證明錯誤不存在。對於你無法窮舉測試的演算法，唯有證明才能讓你真正信任它。