Decision-Procedure Specification¶
Document — instantiates Decision-Procedure Boundary Mapping
Pins down, in writing, the algorithm a decision rests on: exactly which inputs it accepts, what each output means, that it always halts, and why its answers are correct.
The specification is the authoritative contract for a procedure that triage has already judged worth building. Where the worksheet decides that a branch is decidable, the specification says exactly how — nailing the input encoding, the meaning of every permitted output, the guarantee that the procedure halts, and the warrant that its yes and no are actually correct. Its defining discipline is that nothing is left implicit: a reader — or a downstream contract, or an API consumer — can tell precisely what the procedure claims to decide and, just as importantly, what falls outside its accepted inputs.
Example¶
A team ships a linter rule that promises to flag "any function that can divide by zero." Months later it misses a case, a customer is burned, and the fix turns out not to be a patch but a decision-procedure specification for the rule. The spec states the input encoding: the rule accepts functions written in a restricted subset — no reflection, no runtime-loaded code, integer literals and named constants only. It states the predicate and outputs: for an in-subset function it returns safe, unsafe, or unsupported — three distinct answers, not two. It states the termination guarantee: the analysis is a bounded walk over a finite control-flow graph, so it always halts. And it states the correctness warrant: soundness — every function it calls safe provably cannot divide by zero, at the price of some safe-looking code being conservatively marked unsupported. The burned customer's function had used runtime-loaded code; under the spec it is now visibly unsupported rather than silently safe. The specification did not make the tool smarter — it made the tool's boundary honest.
How it works¶
The specification is a written artifact with four non-negotiable sections. It documents claims; it does not prove them (that is the review) and does not choose the scope (that is triage):
- Fix the input encoding contract — the exact form of accepted inputs and what is rejected as out-of-encoding.
- Enumerate the outputs and their meanings — keeping
unknown,unsupported, andtimeoutdistinct from a genuineno. - State the termination guarantee — with the argument sketch behind it: bounded search, finite state, or structurally decreasing recursion.
- State the correctness warrant — what makes yes and no trustworthy: soundness, completeness, or both, and precisely where each is traded away.
Tuning parameters¶
- Encoding strictness — how narrow the accepted input class is. Narrower is easier to guarantee but rejects more real inputs into the
unsupportedlane. - Output granularity — two answers versus a richer set (safe / unsafe / unknown / unsupported / timeout). More states are more honest but push complexity onto every consumer.
- Warrant strength — an informal argument, a structured contract, or a machine-checked proof. A stronger warrant costs more and is exactly what the proof review later tests.
- Soundness / completeness stance — which side you sacrifice when you cannot have both. A sound-but-incomplete analyzer over-marks
unsupported; a complete-but-unsound one risks falsesafe. - Versioning discipline — how tightly the spec is pinned to the implementation, so that predicate drift is caught rather than discovered in the field.
When it helps, and when it misleads¶
Its strength is converting a marketing promise ("we decide X") into an auditable contract with an explicit outside — which is what makes edge cases, API semantics, and support boundaries tractable at all. Its failure mode is over-claiming: writing a spec that promises to decide a property that is, in full generality, undecidable, which is the reason mature analyzers restrict their input subset or settle for sound approximation. Rice's theorem[n1] is the wall here — any non-trivial semantic property of arbitrary program behavior has no total decision procedure — so a spec that quietly promises one is writing a check it cannot cash. The classic misuse is subtler: a spec whose predicate says one thing while the implementation drifts to another, so "correct per spec" and "correct in fact" diverge silently. The guarding discipline: keep unsupported and timeout as first-class outputs, state the soundness/completeness trade explicitly, and treat the spec as the very thing the proof review is licensed to falsify — never as a self-certifying document.
How it implements the components¶
input_encoding_contract— the section that fixes exactly which inputs are accepted and what is rejected as out-of-encoding.decision_predicate— enumerates the permitted outputs and their precise meanings, holdingunknownandunsupportedapart fromfalse.termination_guarantee— records the halting argument (bounded, finite, or structurally decreasing) as a stated, checkable claim.correctness_warrant— states what makes yes and no trustworthy (soundness, completeness) and where each is traded away.
It documents the termination and correctness claims but does not verify them — that falsification is the Termination & Totality Proof Review's job. It takes its scope from the Decidability Triage Worksheet rather than setting it, and leaves the boundary ledger to the Fallback Mode Register.
Related¶
- Instantiates: Decision-Procedure Boundary Mapping — the specification is the artifact that makes a decidable branch concrete and contractable.
- Consumes: Decidability Triage Worksheet — a spec is written only for a branch the worksheet has already judged decidable and worth building.
- Sibling mechanisms: Decidability Triage Worksheet · Termination & Totality Proof Review · Reduction Boundary Map · Fallback Mode Register
Editorial Notes¶
Form Classification¶
Form family: Representation, Specification & Plan
Rationale: Decision-Procedure Specification operates as a non-executable information artifact that externalizes static or prospective structure because it pins down, in writing, the algorithm a decision rests on: exactly which inputs it accepts, what each output means, that it always halts, and why its answers are correct.
Independent corroboration: The frozen evidence defines Decision-Procedure Specification as 'Pins down, in writing, the algorithm a decision rests on: exactly which inputs it accepts, what each output means, that it always halts, and why its answers are correct', so its operative form is Representation, Specification & Plan.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Specialized
Rationale: Formal methods and algorithm design cohered specifications that define accepted inputs, output meanings, termination, correctness guarantees, and deliberate behavior outside the decidable scope.
Related originating lineages:
- Mathematics — Computability and proof theory supplied termination and correctness warrants and limits such as Rice's theorem.
Review resolution: Formal methods and algorithm design cohered specifications that define accepted inputs, output meanings, termination, correctness guarantees, and deliberate behavior outside the decidable scope.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Rice's theorem — every non-trivial property of the behavior (the partial function) computed by an arbitrary program is undecidable. It is why a sound static analyzer must either restrict its input language or answer conservatively (unsupported, or a deliberate over-approximation) rather than promise an exact yes/no for all code. ↩