# Algorithm correctness

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

Algorithm correctness separates partial correctness from termination; total correctness requires both.

mko-algorithm-correctness · concept · v0.10.0



## Mathematical statement

Relative to initial conditions and a postcondition, partial correctness says every halt reached from a legal initial state satisfies the postcondition. Termination says every legal execution eventually reaches a halt. Total correctness is their conjunction.





## Representative formula (exact TeX)

P\land T





## Assumptions


- Use the preceding finite-state model, treating Halt states as execution endpoints.
- For a nondeterministic model, obligations concern every possible execution; one successful path is insufficient.





## Symbol scope


- P — partial-correctness proposition
- T — termination proposition





## Intuition, definition, and misconceptions

An invariant must hold initially and be preserved by every step; satisfaction at a few sample states is insufficient.

Partial correctness permits no execution to halt. Vacuous partial correctness therefore cannot be presented as total correctness.

A complete reachable graph checks bad halts, stuck states and nonhalting cycles in a finite model. General programs still need suitable proof methods.

Correct outputs with possible nontermination, or one successful trace, do not establish total correctness.





## Adopted derivation guide

[Algorithm correctness: partial correctness, termination and total correctness of nondeterministic adjacent-swap sorting](https://ocme.evemisslab.com/en/derivations/derivation-mko-algorithm-correctness-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Abstract computational model](https://ocme.evemisslab.com/en/mko/mko-computational-model/) — Correctness is relative to explicit state and step semantics.
- [Proposition](https://ocme.evemisslab.com/en/mko/mko-proposition/) — Preconditions, postconditions, invariants and obligations are propositions.
- [Mathematical proof](https://ocme.evemisslab.com/en/mko/mko-proof/) — Invariance and termination require separate proof obligations.





## Verification boundary

Complete finite enumeration proves only that model; it does not verify source programs, compilers or unbounded inputs.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Construct Hoare-style specifications, ranking functions, nondeterministic fairness conditions and semantic bridges to real programs.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/algorithm-correctness.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-algorithm-correctness/index.md)