Algorithm correctness

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

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 — Correctness is relative to explicit state and step semantics.
• Proposition — Preconditions, postconditions, invariants and obligations are propositions.
• Mathematical 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.