Termination & Totality Proof Review¶
Test or assessment — instantiates Decision-Procedure Boundary Mapping
Stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return.
This is the adversarial check that a decision procedure is actually total — that there is no in-scope input on which it loops forever, crashes, or returns something outside its declared answer set. Where the specification claims termination and correctness, the proof review tries to break those claims across the whole question class. Its defining stance is totality over the scope: not "it works on the examples" but "there is no in-scope input for which it fails to halt with a permitted answer."
Example¶
A benefits agency runs a rules engine that returns eligible, ineligible, or needs-review for each application. Before rollout it goes to a termination-and-totality proof review. The reviewer ignores the happy path entirely and hunts for the inputs that break totality: a household with zero declared members (does the per-member loop terminate?), an application whose income field is present but negative, a dependency between two rules that could ping-pong forever. Two findings surface. On empty households the engine falls through and returns nothing — a totality gap, an input in scope with no permitted output. And a mutual reference between the "primary earner" and "dependent" rules can loop on an unusual family structure — a termination gap. Both are closed by adding a ranking measure to rule evaluation and a catch-all route to needs-review. Now every application in scope provably lands on exactly one of the three allowed answers.
How it works¶
It is an assessment, not an authoring step: it consumes a specification and tries to falsify its guarantees.
- Take the declared scope and answer set as fixed targets — the review verifies against them, it does not get to redefine them.
- Termination — hunt for unbounded loops and recursion; demand a well-founded measure that strictly decreases, or a provably finite search space.
- Totality of output — hunt for in-scope inputs that fall through, crash, or return outside the permitted answer set.
- Adversarial and edge inputs — empty, extreme, malformed-but-in-encoding, and self-referential cases where totality tends to fail.
- Verdict — total over the stated scope, or not, and if not, the specific counterexample that breaks it.
Tuning parameters¶
- Assurance level — informal inspection, property-based testing, or a machine-checked proof. Higher assurance costs more; reserve full proofs for high-stakes, irreversible decisions.
- Scope of the totality claim — the whole input class or a restricted subset. A narrower verified scope is easier to guarantee but shifts more inputs into the fallback lane.
- Counterexample effort — how hard the reviewer hunts for breaking inputs — random, structured, or genuinely adversarial.
- Measure discipline — whether termination must be shown by an explicit ranking function or an informal "it's obviously finite." Explicit measures catch the subtle non-terminations.
- Re-review trigger — whether any change to the predicate or encoding forces a fresh review rather than a trusted delta.
When it helps, and when it misleads¶
Its strength is that it stops a merely-terminating script from masquerading as a valid decision procedure, converting "seems to work" into "no in-scope input breaks it." The honest failure mode is proving the wrong half — showing that the procedure halts and calling the job done, when a halting procedure can still return a wrong or out-of-range answer. Termination is not correctness. The classic misuse is exactly this conflation, blessed by a wall of green tests on the happy path. Termination itself is best shown the disciplined way, by a well-founded ranking measure[n1] that strictly decreases with no infinite descent — but a ranking function guarantees only that the procedure stops, never that where it stops is right. The guarding discipline: review termination and output-totality as two separate obligations, always over the whole declared scope, and treat any fall-through as a defect rather than an implicit no.
How it implements the components¶
question_class_scope— the totality claim is quantified over the declared class; the review's entire force is "for every in-scope input," so the scope is what it tests against.termination_guarantee— it verifies, or refutes, that the procedure halts on all in-scope inputs, demanding a well-founded measure or a finite space.correctness_warrant— it checks that when the procedure halts it returns a permitted, correct answer, hunting for fall-throughs and out-of-range outputs.
It does not define the input encoding or the predicate it tests against — those come from the Decision-Procedure Specification. It does not classify the problem's complexity (that is the Reduction Boundary Map), nor govern what happens to the cases it fails (that is the Fallback Mode Register).
Related¶
- Instantiates: Decision-Procedure Boundary Mapping — the review is the assurance step that turns a stated procedure into a trusted one.
- Consumes: Decision-Procedure Specification — the review verifies the termination and correctness claims the specification states.
- Sibling mechanisms: Decidability Triage Worksheet · Decision-Procedure Specification · Reduction Boundary Map · Fallback Mode Register
Editorial Notes¶
Form Classification¶
Form family: Assessment, Review & Assurance
Rationale: Termination & Totality Proof Review operates as a bounded evaluation of existing evidence or work that produces a finding or disposition because it stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return.
Independent corroboration: The frozen evidence defines Termination & Totality Proof Review as 'Stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return', so its operative form is Assessment, Review & Assurance.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Mathematics
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: The defining operation is: Stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return. In the mathematics lineage, that operation is specifically evidenced by authoritative or primary work that grounds mathematical proof of software properties, including total correctness claims that require termination and permitted results. This makes mathematics the best historical origin, while the retained alternates document contributing methods and later applications rather than being mistaken for coequal origins.
Related originating lineages:
- Computer Science & Software Engineering — Computer science and software-engineering practice supplies a parallel or contributing lineage for the mechanism's defining operation: stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return.
- Organizational & Management Science — organizational_management supplies a historically relevant parallel or contributing practice for the defining operation—Stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return—but the evidence does not make it the best primary lineage.
- Philosophy — Philosophical logic, epistemology, and normative reasoning supplies a parallel or contributing lineage for the mechanism's defining operation: stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return.
- Systems Thinking & Cybernetics — Systems science's feedback, stock-flow, boundary, and regulation tradition provides a formative adjacent lineage for the same termination and totality proof review operation.
Review resolution: The blind reviewers disagree on primary lineage (organizational_management versus mathematics), so I adjudicated the mechanism rather than inheriting either label. The defining operation is: Stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return. In the mathematics lineage, that operation is specifically evidenced by authoritative or primary work that grounds mathematical proof of software properties, including total correctness claims that require termination and permitted results. This makes mathematics the best historical origin, while the retained alternates document contributing methods and later applications rather than being mistaken for coequal origins. The cited NIST Formal Methods and Combinatorial Testing directly supports the mechanism-specific operation and its disciplinary lineage. I retain all independently explained historical alternates without a numeric cap. origin_mode=single_lineage records how the mechanism arose; domain_reach=specialized separately records how broadly it can now be applied.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Researched adjudication after independent review; high confidence.
Sources consulted:
Notes¶
[n1] A termination proof by well-founded (or structural) recursion exhibits a measure — a "rank" — that maps each step into a well-ordered set and strictly decreases on every recursive call. Because a well-ordered set has no infinite descending chain, the procedure cannot recurse forever. It shows only that the procedure stops, not that its answer is correct — which is why totality of the output is a separate check. ↩