# 算法正確性

算法正確性分開部分正確性與終止性；總正確性需要兩者同時成立。

mko-algorithm-correctness · concept · v0.10.0



## 數學敘述

相對初始條件與後置條件，部分正確性表示每個從合法初始狀態到達的停止狀態都滿足後置條件；終止性表示每個合法執行最終到達停止狀態；總正確性是兩者的合取。





## 代表公式（精確 TeX）

P\land T





## 成立條件


- 使用前一條目的有限狀態模型，Halt 狀態視為執行終點。
- nondeterministic 模型要求所有可能執行滿足責任；一條成功路徑不足以證明。





## 符號作用域


- P — 部分正確性命題
- T — 終止性命題





## 直觀、定義與常見誤解

不變量需在初始狀態成立，且每一步保持；只在幾個 sample state 成立不夠。

部分正確性允許沒有執行終止；因此 vacuous partial correctness 不能冒充總正確。

有限狀態模型的全部可達圖可以核對錯誤 halt、stuck 與非停止 cycle；一般程式仍需要適合的 proof method。

把輸出正確但可能不停止，或一條成功 trace，當成總正確性。





## 已採用的推導導讀

[算法正確性：非確定性相鄰交換排序的部分正確、終止與總正確](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-algorithm-correctness-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [抽象計算模型](https://ocme.evemisslab.com/zh-Hant/mko/mko-computational-model/) — 正確性相對明示狀態與步驟語義。
- [命題](https://ocme.evemisslab.com/zh-Hant/mko/mko-proposition/) — 前置、後置、不變量與責任都是命題。
- [數學證明](https://ocme.evemisslab.com/zh-Hant/mko/mko-proof/) — 不變量與終止性需要分離的證明義務。





## 驗證界線

有限模型完整枚舉只證該模型；不等於來源程式、編譯器或無界輸入已驗證。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

建立 Hoare-style 規格、ranking function、nondeterministic fairness 與實際程式語義橋。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/algorithm-correctness.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-algorithm-correctness/index.md)