Formal Decidability Probe¶
Formal test — instantiates Dispute-Question Alignment
For a question handed to an automated or formal decider, tests whether it actually admits a terminating decision procedure — or whether the promised verdict is impossible.
Sometimes a dispute is routed to a forum that promises a mechanical answer — a rule engine, an algorithm, a formal proof system that will "just decide it." The Formal Decidability Probe is the check that asks whether that promise can be kept. Before anyone runs the decider, it tests whether the question, exactly as posed, admits an effective, terminating decision procedure: is there an algorithm that always halts with the demanded answer, or is the question undecidable, only semi-decidable (halts on some answers but not others), or decidable in principle yet computationally intractable? Its defining move is to treat decidability itself as the prior question. If the demanded answer form — a guaranteed, total yes/no verdict — exceeds what any procedure can deliver for this class of question, the probe says so, and the promised automatic settlement is revealed as impossible rather than merely hard. It is the archetype's guard against the formalization trap: the belief that dressing a question in formal clothing makes it computable.
Example¶
A security team is adding a rule to an automated access-control engine, and the vendor claims the engine can decide, for any policy, whether some sequence of permitted administrative actions could ever let an untrusted account acquire administrator rights — a blanket "no forbidden state is ever reachable" guarantee. The Formal Decidability Probe tests that promise before the engine is trusted. In the general access-matrix protection model this safety question — whether a right can ever leak to a subject that should not hold it — is undecidable: no algorithm always halts and answers it for arbitrary policies over unbounded action sequences.[1] So the engine cannot deliver the total, terminating guarantee it advertises, and the demanded answer form is unattainable as stated.
But the probe does not stop at "impossible." It records what is attainable. Restrict the model — monotonic policies, a bounded number of subjects and operations — and safety becomes decidable, so the engine can return a real verdict within that fragment. Relax the answer form to a bounded check — "no forbidden state is reachable within N administrative operations" — and the engine becomes a genuine early-warning tool, honest about the horizon past which it cannot certify. Because a leak, if one exists, can be found by search while its absence cannot be proved in general, the engine can refute safety but not confirm it for an arbitrary policy. The probe's note reframes the purchase: blanket "provably safe" claims are false; the engine catches many leak paths, and safety beyond the decidable fragment is a governance judgment, not a computation.
How it works¶
- Locate the promised decider. Identify the formal system, algorithm, or rule set that is being asked to return a terminating verdict, and the exact predicate it is meant to decide.
- Classify the question's decidability. Determine whether an effective, always-halting procedure exists for the question as posed (decidable), one that halts only on positive instances (semi-decidable), or none at all (undecidable) — and, separately, whether a decidable question is nonetheless intractable in practice.
- Compare answer form to decidability class. Hold the demanded answer form — a total, terminating verdict — against what the class actually permits, and flag the gap where the two do not match.
- Emit the note and the honest remedy. Record the finding and pair every impossibility with a usable alternative: restrict to a decidable fragment, downgrade to a semi-decision or bounded check, or hand the question off to human judgment.
Tuning parameters¶
- Formalization depth — how rigorously the question is modeled before the verdict, from a full reduction proof to a heuristic argument. Deeper analysis is more trustworthy but costs specialist effort.
- Fragment restriction — how far the question is narrowed to buy decidability. More restriction guarantees a terminating answer but trades away the generality the disputants may actually care about.
- Semi-decision tolerance — whether a one-sided procedure (can refute but not confirm, or vice versa) counts as good enough for the decision at hand.
- Resource bound — for decidable-but-intractable cases, the compute and time budget that stands in for "terminating." A generous bound answers more cases but blurs the line with true undecidability.
- Conservatism — whether an ambiguous case defaults to "treat as undecidable and hand off" or "attempt the procedure anyway." Conservative defaults avoid false promises but can abandon tractable instances.
When it helps, and when it misleads¶
Its strength is that it dissolves a specific illusion: that a hard, contested question becomes settleable simply by handing it to a machine that "decides." Undecidability is a hard wall, not a resourcing problem, so where the probe applies it is decisive — it separates the questions a procedure can genuinely close from those merely dressed up as computable, and it protects a formal process from promising a terminating decision it cannot deliver.
Its failure mode is the mirror image: over-application. A general impossibility result gets invoked to duck a question that is perfectly decidable in the restricted, finite instance at hand — declaring a small, concrete policy "undecidable" because the unrestricted problem is, using the wall as an alibi. Confusing intractable with undecidable does the same, abandoning a question a bigger budget would settle. The guarding discipline is to distinguish "undecidable in general" from "undecidable for this concrete instance," and to pair every impossibility finding with the largest decidable fragment that is available.
How it implements the components¶
The probe is the archetype's decidability instrument — the narrowest subset, invoked only where a mechanical verdict is promised:
formal_decidability_note— its core output: a recorded finding that the question, under the promised procedure, is decidable, semi-decidable, undecidable, or decidable-but-intractable.answer_form_constraint— it tests whether the demanded answer form (a total, terminating verdict) is attainable and, if not, constrains it to what a procedure can actually deliver — a decidable fragment or a semi-decision — rather than dictating the answer's rhetorical shape or proof standard.
It does not gather or type the claims it evaluates (see Fact-Definition-Quality-Policy Matrix), bind evidence standards and burdens to a question (Burden and Standard Alignment Table), or decide which human forum is competent (Jurisdictional Stasis Routing Check).
Related¶
- Instantiates: Dispute-Question Alignment — the probe is the check applied when a question is routed to a formal system that promises a terminating decision.
- Consumes: Jurisdictional Stasis Routing Check — the probe runs on questions the routing check has assigned to a formal or automated decider, testing whether that forum can actually deliver the verdict it promises.
- Sibling mechanisms: Stasis Mapping Workshop · Fact-Definition-Quality-Policy Matrix · Point-at-Issue Intake Form · Cross-Stasis Dialogue Protocol · Burden and Standard Alignment Table · Jurisdictional Stasis Routing Check · Stasis Review Memo
Editorial Notes¶
Form Classification¶
Form family: Assessment, Review & Assurance
Rationale: Formal Decidability Probe operates as a bounded evaluation of existing evidence or work that produces a finding or disposition because it for a question handed to an automated or formal decider, tests whether it actually admits a terminating decision procedure — or whether the promised verdict is impossible.
Independent corroboration: The frozen evidence defines Formal Decidability Probe as 'For a question handed to an automated or formal decider, tests whether it actually admits a terminating decision procedure — or whether the promised verdict is impossible', so its operative form is Assessment, Review & Assurance.
Nearest alternative: Analysis, Modeling & Optimization — The probe evaluates whether a promised formal decider exists and returns a decidability classification, rather than merely deriving a theorem.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Multi-domain
Rationale: Whether a terminating decision procedure exists is the canonical problem of computability theory.
Related originating lineages:
- Mathematics — Mathematical logic supplies undecidability proofs and formal-system foundations.
- Philosophy — Logic and philosophy of computation materially shape the distinction between a well-posed formal question and an unattainable verdict.
Review resolution: Both reviewers agree that computer_science is primary. I retain mathematics, philosophy only as formative origin lineage(s), without treating every later application as an origin. cross_disciplinary_synthesis is appropriate because the exact artifact combines contributions from multiple professional lineages. Reach is multi_domain as a separate applicability judgment: it does not widen or narrow the recorded provenance. Encyclopedia synthesis is false because the artifact is already established enough that encyclopedia-specific synthesis is not required. The secondary differences are reconciled with no unresolved primary-provenance ambiguity.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
The probe is the rarest mechanism in the set to fire: most disputes never route a question to a decider that promises to terminate, so most never need it. But where a process does stake its legitimacy on an automatic decision — a compliance engine, a smart contract, a proof-checked rule — the probe is the difference between a defensible terminating procedure and a promise the procedure cannot keep.
References¶
[1] The safety problem for the general access-matrix protection model — whether a given access right can ever be leaked to a subject through some sequence of allowed operations — was proved undecidable by Harrison, Ruzzo, and Ullman (1976). Restricted models (mono-operational or otherwise bounded systems) regain decidability, which is why a decidability probe pairs the impossibility finding with the fragment that is still checkable. withdrawn registry ↩