Skip to content

Decidability Computability

Version
v1 · 2026-08-24 · History
Prime #
780
Origin domain
Computer Science & Software Engineering
Subdomain
computability theory → Computer Science & Software Engineering
Also from
Mathematics

Core Idea

A class of yes/no questions is decidable when a finite, mechanical procedure always terminates with the correct answer on every instance. The prime carves a sharp boundary — not in practice but in principle — between questions a rule can settle and questions no procedure ever can. Three things must travel together: the question class, the candidate procedure, and the termination guarantee; lose any one and decidability fails.

How would you explain it like I'm…

The Always-Works Recipe

Imagine a yes-or-no question, like 'is this number even?' For some questions there's a simple recipe a machine can follow that ALWAYS finishes and ALWAYS gives the right yes or no. For other kinds of questions, no such recipe can ever exist — not because the machine is slow, but because there just isn't one.

Yes-Or-No, Every Time

Take a whole FAMILY of yes-or-no questions — not one question, but every question of a certain kind. That family is 'decidable' if there's one fixed step-by-step recipe that, given any question in the family, always stops and gives the correct yes or no. The key word is 'always': it can't sometimes run forever, and it can't sometimes guess wrong. If a recipe usually answers but sometimes loops forever, that's not good enough; if it always stops but sometimes lies, that's not good enough either. Decidable means a recipe exists that does both — finishes, and is right — for every question in the family.

The Decidable Boundary

A class of yes/no questions is decidable when there exists one fixed mechanical procedure that, given ANY instance from the class, always halts in finite time and always returns the correct answer. Three things must travel together: the question class, the candidate procedure, and the guarantee that it terminates — lose any one and decidability fails. The way it fails is informative: a procedure that answers sometimes but loops forever otherwise is only semi-decidable; one that always halts but is only sometimes right is a heuristic; one that handles some instances but not the whole class is just a special-case solver. Note this is about the WHOLE class, not a single question — so it's a property of, say, an entire logical theory. And it's not the same as being easy: a decidable question can still be astronomically expensive to settle, while an undecidable one can't be settled at any cost.

 

Decidability is the property of a class of yes/no questions that admits a finite, mechanical procedure which, applied to any instance, always terminates and returns the correct answer. The prime carves a sharp boundary — not 'hard in practice' but 'impossible in principle, even with unbounded patience' — and it does so by insisting three components travel together: the question class, the would-be procedure, and the termination guarantee. Drop any one and decidability fails, and the failure mode is diagnostic: semi-decidable (answers sometimes, else loops), heuristic (always halts, only sometimes correct), or special-case solver (handles part of the class, not the whole). This question-class/procedure/termination skeleton gives the prime its reach, recurring whether the 'theory' is a fragment of arithmetic, a body of clinical criteria, or a statutory regime. From the logic side the question class is a theory and the uniform question is theoremhood — is there one fixed algorithm that halts and correctly reports provability for every formula? Decidability is thus a property of the whole theory, and the boundary can cut between theories that look superficially alike. Crucially, decidability separates cleanly from tractability: the claim is that no guaranteed finite procedure classifies the whole class, a claim about the structure of the question, not the resources brought to bear.

Broad Use

  • Computability theory: the halting problem and the Entscheidungsproblem — the procedure a Turing machine, termination its halting with a verdict.
  • Mathematical logic: Presburger arithmetic is decidable, Peano arithmetic undecidable — a property of the whole theory, not any one formula.
  • Law: justiciability asks whether a court can resolve a dispute by applying rules to facts; the political-question doctrine declares some questions structurally undecidable.
  • Clinical diagnosis: a criterion is operational when a trained clinician reaches a stable yes/no in finite time; pre-checklist psychiatry was undecidable in this sense.
  • Engineering verification: model checking decides safety on finite-state models, while theorem proving over richer logics is undecidable.
  • Standards and compliance: vague standards make compliance undecidable in practice and shift power to whoever interprets them.

Clarity

It separates hard from undecidable: a chess position is hard but decidable (the tree is finite); the halting problem is undecidable regardless of resources. It also keeps distinct the semi-decidable middle, where a procedure halts on "yes" but may loop forever otherwise.

Manages Complexity

Carving out a decidable subclass, automating it, and pushing the residual into an explicit judgment bucket is one of the cleanest forms of complexity reduction — and it stops the wasted effort of seeking a procedure that provably cannot exist.

Abstract Reasoning

It supports a small family of moves: classify the class (decidable / semi-decidable / undecidable), restrict it to recover decidability, distinguish class from instance, and locate the irreducible judgment honestly rather than disguising it as procedure.

Knowledge Transfer

  • Logic → reform: the operationalization-or-not test — is there a procedure any trained operator can run? — reframes whole reform programs; a checklist criterion, bright-line rule, and machine-verifiable standard are the same move.
  • Logic → clinical/grading: the operator-invariance check is inter-rater reliability under another name, porting from criteria to rubrics to arbitration.

Example

Pre-checklist psychiatry asked "is this patient neurotic?" — undecidable by any procedure two clinicians would run alike, yielding low inter-rater agreement. Structured criteria ("five of nine symptoms, two weeks") narrowed the class to a decidable subset, recovering operator-invariance, while the adjacent question "how best to help this patient?" was honestly left judgment-bound.

Relationships to Other Abstractions

Local relationship map for Decidability ComputabilityParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.DecidabilityComputabilityPRIMEPrime abstraction: Computability — is a kind of, typicalComputabilityPRIMEDomain-specific abstraction: Model Checking — presupposesModel CheckingDOMAINDomain-specific abstraction: Conjugacy problem — is a kind ofConjugacyproblemDOMAINDomain-specific abstraction: Entscheidungsproblem — is a kind ofEntscheidungspr…DOMAINDomain-specific abstraction: Matrix mortality problem — is a kind ofMatrix mortalityproblemDOMAINDomain-specific abstraction: Planarity testing — is a kind ofPlanaritytestingDOMAIN

Current abstraction Decidability Computability Prime

Parents (1) — more general patterns this builds on

  • Decidability Computability is a kind of, typical Computability Prime

    'Logical decidability is one instance of the computability partition' — decidability concerns a formal system's mechanical settleability; computability is the broader medium-neutral boundary.

Children (5) — more specific cases that build on this

  • Conjugacy problem Domain-specific is a kind of Decidability Computability

    The proposed strict upward parent is prime:decidability_computability.

  • Entscheidungsproblem Domain-specific is a kind of Decidability Computability

    The proposed strict upward parent is prime:decidability_computability.

  • Matrix mortality problem Domain-specific is a kind of Decidability Computability

    The proposed strict upward parent is prime:decidability_computability.

  • Planarity testing Domain-specific is a kind of Decidability Computability

    The proposed strict upward parent is prime:decidability_computability.

  • Model Checking Domain-specific presupposes Decidability Computability

    Model checking presupposes decidability because its push-button verdict relies on restricting the model and property to a class with a uniform terminating correct procedure.

Hierarchy paths (2) — routes to 2 parentless roots

Not to Be Confused With

  • Decidability is not Computability because computability asks whether any procedure solves a problem at all, whereas decidability strengthens this to a total, two-sided guarantee — halting with the correct yes/no on every instance; the gap is the semi-decidable middle.
  • Decidability is not Complexity because complexity asks how costly a decidable question is to settle, whereas decidability asks whether any terminating procedure exists; a decidable question can be astronomically expensive.
  • Decidability is not Algorithm because an algorithm is a concrete procedure for a task, whereas decidability is the existence claim that a uniformly-terminating-and-correct procedure exists for a whole class.