Computability

Version

v1 · 2026-08-24 · History

Prime #

722

Origin domain

Computer Science & Software Engineering

Subdomain

theory of computation → Computer Science & Software Engineering

Aliases

Church Turing Thesis

Core Idea

Computability is the question — and the line it draws — between problems for which an effective procedure exists and problems for which none does. A problem is computable, in the classical sense captured equivalently by Turing machines, the λ-calculus, μ-recursive functions, and a dozen other formalisms unified by the Church–Turing thesis^[1], exactly when some mechanical procedure, given any well-formed instance, terminates in finite time with the correct answer. A problem is uncomputable when no such procedure exists — and the force of the claim is that this is so not by accident or by current limitation, but in principle. The line is not a function of how clever the engineer is; it is a structural feature of the problem itself, demonstrated by diagonal arguments and reductions that survive every refinement of the underlying machine model. No future increase in speed, memory, or ingenuity moves an uncomputable problem to the computable side, because the impossibility is a property of the problem, not of the apparatus.

The structural commitment is small but radical: some questions admit no procedural answer at all. The halting problem, the Entscheidungsproblem, Hilbert's tenth problem, Rice's theorem on non-trivial semantic properties of programs, the busy-beaver function, and the Kolmogorov-complexity function are not "hard" in the resource-budget sense^[2]; they are impossible in the strict sense that no algorithm exists. Three further structural features travel with the computability role. Self-reference and diagonalization: uncomputability proofs almost universally run the move "consider a procedure that would solve the problem, then apply it to its own description," the same diagonal that Cantor, Gödel, Turing, and Tarski each deploy at different levels^[3], with the take-away that any sufficiently expressive procedural system can pose questions about itself it cannot answer. Degrees of unsolvability: the uncomputable problems are not all equally unsolvable but form a hierarchy (the Turing degrees, the arithmetical hierarchy) ordered by relative computability^[4], so that "unsolvable" acquires internal texture. The procedure–problem asymmetry: an algorithm is a positive object one can exhibit, whereas uncomputability is a negative result one must prove, and the recognition that "no procedure of any kind exists" is a far stronger claim than "I cannot think of one" is itself a transferable structural insight.

How would you explain it like I'm…

No Recipe Exists

Some problems you can solve by following a recipe step by step until you're done. But a few problems are special: there is NO recipe that always finishes with the right answer, no matter how clever or fast you are. It's not that the recipe is hard to find — it's that one simply doesn't exist.

Some Questions Have No Recipe

A computer follows recipes — exact step-by-step instructions. Computability is about the line between problems a recipe CAN solve and problems where no recipe can possibly work. The surprising part: for some problems, it's not that the recipe is slow or that we haven't found it yet — it's that no recipe can EXIST, ever, no matter how fast or powerful the machine. One famous example is trying to build one program that looks at any other program and always tells you whether it will eventually stop running or loop forever. You can prove no such program can be built. Faster computers don't help, because the wall is in the problem itself, not the machine.

The Impossible-In-Principle Line

Computability draws the line between problems an effective procedure can solve and problems where none can exist. A problem is computable when some mechanical procedure — captured equally well by Turing machines, the lambda-calculus, or recursive functions, all unified by the Church-Turing thesis — halts in finite time with the correct answer for any instance. The force of 'uncomputable' is that it's impossible in principle, not just hard: no increase in speed, memory, or cleverness moves a problem across the line, because the impossibility is a property of the problem, not the machine. The proofs use diagonalization — 'imagine a procedure that solves it, then feed it its own description' — the same move Cantor, Godel, and Turing each used. And the uncomputable problems aren't all equally bad; they form a hierarchy of 'degrees,' so unsolvability itself has internal structure. Crucially, an algorithm is something you can exhibit, but uncomputability is something you must PROVE — 'no procedure of any kind exists' is far stronger than 'I can't find one.'

 

Computability is the question — and the line it draws — between problems for which an effective procedure exists and problems for which none does. A problem is computable, in the classical sense captured equivalently by Turing machines, the lambda-calculus, mu-recursive functions, and a dozen other formalisms unified by the Church-Turing thesis, exactly when some mechanical procedure, given any well-formed instance, terminates in finite time with the correct answer. It is uncomputable when no such procedure exists — and the force of the claim is that this holds not by accident or current limitation but in principle: no future gain in speed, memory, or ingenuity moves an uncomputable problem to the computable side, because the impossibility is a structural feature of the problem, demonstrated by diagonal arguments and reductions that survive every refinement of the machine model. The halting problem, the Entscheidungsproblem, Hilbert's tenth problem, Rice's theorem, and the busy-beaver function are not merely hard but strictly impossible. Three features travel with the role: self-reference and diagonalization (consider a procedure that solves the problem, then apply it to its own description — Cantor, Godel, Turing, and Tarski all run this move); degrees of unsolvability (the uncomputable problems form a hierarchy — the Turing degrees, the arithmetical hierarchy — ordered by relative computability); and the procedure-problem asymmetry (an algorithm is a positive object you exhibit, whereas uncomputability is a negative result you must prove, and 'no procedure of any kind exists' is a far stronger claim than 'I cannot think of one').

Structural Signature

the class of well-posed questions — the class of admissible effective procedures — the solvable/unsolvable partition — the in-principle (not resource-bounded) character of the boundary — the self-reference/diagonalization engine — the model-invariance of the line

A configuration exhibits a computability boundary when each of the following holds:

• A question class. There is a well-defined family of instances, each with a definite correct answer, posed precisely enough that "solving it" is meaningful.
• A procedure class. There is a notion of admissible effective procedure — a mechanical recipe that, given an instance, may terminate with the correct answer — fixed independently of any single machine.
• A solvable/unsolvable partition. The question class splits into instances some procedure decides and instances no procedure decides; membership on the unsolvable side is a property of the problem, not of the solver's ingenuity.
• In-principle impossibility. The boundary is not about speed, memory, or cleverness; no quantity of resources moves an unsolvable problem across it. "No procedure exists" is categorically stronger than "I found none."
• A self-reference engine. The negative side is established by diagonalization or reduction — apply a hypothesized solver to its own description, or encode a known-unsolvable problem inside the target — the same move running through Cantor, Gödel, Turing, and Tarski.
• Model-invariance and internal texture. The line survives every reasonable change of formalism (Church–Turing), and the unsolvable region is itself ordered into degrees of relative unsolvability.

These compose into a boundary diagnosis: fix a question class and a procedure class, ask whether self-reference manufactures an instance no admissible procedure can decide, and — if so — choose among restrict-the-inputs, accept-partiality, or escalate-to-an-oracle.

What It Is Not

• Not algorithm. An algorithm is a positive object — an effective procedure one exhibits; computability is the boundary question of whether such an object can exist at all for a problem class. One is a thing you build, the other a partition between buildable and provably-unbuildable.
• Not complexity. Complexity asks how expensive a solvable problem is within a resource budget (time, space); computability asks whether any procedure exists, regardless of cost. A problem with only astronomically slow algorithms is computable; the halting problem is not, and no budget changes that.
• Not decidability_computability. Decidability concerns whether a question class — including a formal system's validity or provability — is mechanically settleable by a procedure that always halts with the correct verdict; computability is the broader medium-neutral boundary over arbitrary question classes. Decidability is one instance of the computability partition (see decidability_computability).
• Not falsifiability. Falsifiability is an empirical-epistemic criterion about whether evidence could in principle refute a claim; computability is a mathematical claim about procedural answerability. A proposition can be falsifiable yet its decision uncomputable, and vice versa.
• Not constraint. A constraint restricts the admissible solutions to a problem; an uncomputability result is not a restriction one imposes but a structural impossibility one proves, surviving every change of machine model.
• Common misclassification. Calling a merely hard problem "impossible" (abandoning a tractable search), or calling an uncomputable problem "just hard" (throwing more compute at a wall that no resource ever crosses). The catch: ask whether no procedure exists or whether the only procedures are too slow — the first is computability's territory, the second is complexity's.

Broad Use

• Mathematics and logic. The halting problem; Hilbert's tenth (no algorithm decides Diophantine solvability); Gödel's incompleteness as a sibling result driven by the same self-reference engine^[5]; word problems in finitely presented groups; provability predicates.
• Computer science. Verification limits via Rice's theorem (no algorithm decides non-trivial semantic properties of arbitrary programs); undecidable type systems^[6]; the limits of program-equivalence checking and program synthesis.
• Linguistics. The parsing problem for sufficiently general grammars (unrestricted phrase-structure grammars) is undecidable^[7], one structural reason the field works with constrained grammar classes.
• Physics. The spectral-gap problem for certain translation-invariant quantum lattice models is undecidable^[8], and whether some dynamical systems exhibit particular long-run behaviour may be as well.
• Economics and decision theory. The existence of a procedurally computable equilibrium is bounded by computability constraints, and some rational-expectations equilibria can be uncomputable.^[9]
• Law and governance (analogically). Institutional procedures face their own version of the boundary: not every legal question admits a procedural answer from within the current rules, and the system must change its rules or accept the question as outside competence — the institutional analogue of Gödelian incompleteness.
• AI alignment. "Does this network satisfy this property on all inputs?" is, for sufficiently expressive networks and properties, undecidable, so practical verification restricts the property class or the network class.

Clarity

Naming the computability boundary explicitly clarifies a recurring and consequential confusion: the difference between hard but solvable and unsolvable in principle. A programmer struggling with the halting problem learns that the obstacle is not effort or hardware — no advance in speed, no quantum speedup, no improvement in tooling brings the halting problem inside the computable — and this is structural news that re-orients the engineering response from "try harder" to "constrain the problem, accept partiality, or change the question." The same clarification operates in other substrates. A legal system that cannot settle some question from within its current rules is not failing to apply effort; it is bumping against a structural boundary of its own apparatus, and the appropriate responses (legislate, escalate, treat as outside competence) are categorically different from the responses to a merely difficult question. The clarifying force, in every substrate, is to separate the situations in which more procedure will eventually settle a question from the situations in which no amount of procedure ever will — a distinction that, once drawn, changes what counts as a sensible next move.

Manages Complexity

The computability lens partitions the entire universe of well-posed problems into two disjoint regions — those admitting an effective procedure and those not — and this is a dramatic compression of the design space. Once a problem is identified as uncomputable, the analyst stops searching for an algorithm and instead chooses among exactly three structural responses. One may restrict the input class, since a problem undecidable on arbitrary inputs is often decidable on a constrained subset, which is why static analysis works on practical programs even though it cannot work on all programs. One may accept partiality, allowing a procedure that is correct when it terminates but may not terminate on every input, which is the status of semi-decidability and of every proof-search procedure. Or one may shift to an oracle or external arbiter, assuming an outside agent supplies the answer to the uncomputable question and reasoning from there. This restrict / accept-partial / escalate taxonomy is itself a substrate-independent insight: every system bumping against an in-principle limit responds with one of those three moves, and recognizing which one a given tool has chosen makes its guarantees and its blind spots legible. The complexity that the lens manages is the complexity of false hope — the effort that would otherwise be spent seeking an algorithm that provably cannot exist — and redirecting that effort into one of the three principled workarounds.

Abstract Reasoning

Recognizing the computability pattern enables a small family of reasoning moves. Reduction proofs of uncomputability: show that a problem is at least as hard as the halting problem by encoding halting within it, a move whose structure — build a reduction, then appeal to the known negative result — carries across substrates as the general technique of impossibility-by-reduction. Diagonal arguments: encode self-reference and derive a contradiction by applying a supposed solver to its own description, the same move that appears in Cantor's theorem, Russell's paradox, Gödel's incompleteness, and Turing's halting result, each a structural rerun of the others.^[3] Oracle-relative reasoning: assume a solver for some problem and ask what becomes computable given it, which generates the Turing-degree hierarchy and transfers as assumption-relative reasoning elsewhere ("assume the regulator can answer X; what then becomes administratively feasible?"). The Church–Turing closure question: the claim that the boundary is invariant across reasonable model choices imports into other substrates as the question "is this limit fundamental, or merely an artifact of these particular rules?" Each of these is a template stated in terms of procedures, instances, and reductions rather than in terms of any particular computing machinery, which is why each redeploys intact in logic, in physics, in governance, and in alignment.

Knowledge Transfer

The transferable content of computability is a set of structural moves that survive the change of substrate because each is stated at the level of "a class of questions and a class of procedures" rather than at the level of any particular machine. The diagonal self-reference move transfers into institutional review: the Gödel/Turing question "what happens if the procedure is applied to its own description?" reappears as "what does the auditing rule say about auditing itself?", and self-referential failure modes — an oversight body that cannot audit its own conduct, a constitutional clause that purports to prohibit its own amendment — are recognizably diagonal-argument shaped. The reduction move transfers into impossibility arguments: in policy and design, showing "if you could solve X you could solve the known-impossible Y" is the structural analogue of a computability reduction, and the discipline of hunting for a known impossibility to reduce to imports directly. The restrict / accept-partial / escalate taxonomy transfers into engineering and professional posture: every team that builds analysis tools for general artifacts — linters, static analyzers, security scanners, model checkers — is implicitly choosing one of the three workarounds, and the same triad organizes the responses available to a compliance auditor facing an under-specified standard, a clinician facing an ill-posed diagnostic question, or a court facing a non-justiciable dispute. The Church–Turing invariance question transfers into institutional analysis: a regulator who cannot make a determination might be bumping a fundamental limit (the question is genuinely under-determined by the available evidence) or merely an artifact of the current rules (a procedural change would resolve it), and distinguishing the two is the institutional version of asking whether a computability bound is model-dependent. The halting proof itself — assume a decider, build a program that does the opposite of what the decider predicts about it, apply it to its own description, and derive a contradiction — is the paradigm whose shape transfers: self-reference plus negation manufactures an unanswerable question, and the practical consequence (that automatic decision of non-trivial behavioural properties is in-principle impossible, so tools must commit to a soundness/completeness trade-off) is a structural fact that recurs wherever a sufficiently expressive system is asked to decide general properties of its own outputs.

Examples

Formal/abstract

The halting problem is the paradigm case that exhibits every element of the signature end-to-end. The question class is well-posed: given a program \(P\) and an input \(x\), does \(P\) eventually halt on \(x\)? Each instance has a definite correct answer. The procedure class is the admissible effective procedures, fixed model-independently by the Church–Turing thesis. Now suppose, for contradiction, that a total decider \(H(P, x)\) exists that always halts and correctly returns "halts" or "loops." Fire the self-reference engine: construct \(D(P)\) which calls \(H(P, P)\) and then does the opposite^[1] — if \(H\) says \(P\) halts on its own description, \(D\) loops forever; if \(H\) says \(P\) loops, \(D\) halts. Apply \(D\) to its own description: \(D(D)\) halts exactly when \(H(D,D)\) says it loops, and loops exactly when \(H\) says it halts — a contradiction. So \(H\) cannot exist. This establishes the solvable/unsolvable partition, and the impossibility is in-principle, not resource-bounded: no faster machine, no quantum speedup, no extra memory relocates the halting problem to the computable side, because the diagonal contradiction is a property of the problem, not the apparatus. The line is model-invariant — re-running the argument with λ-calculus or μ-recursive functions yields the same boundary — and the unsolvable region has internal texture: relative to a halting oracle, new problems become decidable, generating the Turing-degree hierarchy.

Mapped back: Turing's halting proof instantiates the full computability signature — a precise question class, a model-independent procedure class, a diagonalization engine manufacturing an undecidable instance, in-principle (not resource-bounded) impossibility, and model-invariance with degree structure above the line.

Applied/industry

Static program analysis — linters, type checkers, security scanners, model checkers — is the engineering substrate where the restrict / accept-partial / escalate taxonomy plays out daily, downstream of Rice's theorem (no algorithm decides any non-trivial semantic property of arbitrary programs).^[2] A team building a tool to answer "does this program ever dereference a null pointer?" confronts an in-principle boundary: on arbitrary programs the question is undecidable, so no amount of cleverer engineering yields a tool that is both sound and complete on all inputs. The structural diagnosis reorients the response from "try harder" to one of exactly three principled workarounds. Restrict the input class: analyze only programs in a constrained subset (no unbounded recursion, no dynamic dispatch) where the property becomes decidable — the move behind type systems and bounded model checking. Accept partiality: build a sound-but-incomplete analyzer that flags every real null-dereference plus some false positives, or a complete-but-unsound one that misses some — every practical static analyzer commits to one side of this soundness/completeness trade-off because it cannot have both. Escalate to an oracle: emit warnings for the cases the analysis cannot settle and route them to a human reviewer or a runtime assertion, treating the human as the external arbiter for the undecidable residual. Recognizing which workaround a tool has chosen makes its guarantees legible: a "sound" analyzer's false positives are not bugs to be eliminated but the unavoidable price of staying on the decidable side of an in-principle boundary. The same triad organizes a compliance auditor facing an under-specified standard (restrict scope, flag-and-escalate ambiguous cases, or defer to a regulator's ruling).

Mapped back: Static analyzers and compliance audits both bump an in-principle decidability boundary and respond with the restrict / accept-partial / escalate triad, choosing a soundness/completeness posture rather than seeking a provably-nonexistent complete decider — the computability boundary operating in software-engineering and governance substrates.

Structural Tensions

T1 — In-Principle versus Resource-Bounded (kind-of-impossibility). Computability draws an absolute line — no procedure of any kind, ever — while complexity theory draws a resource line: feasible versus infeasible within a budget. The failure mode runs both directions: treating a merely expensive but decidable problem as "impossible" (abandoning a tractable search), or treating an undecidable problem as "just hard" (throwing more compute at the halting problem forever). Diagnostic: ask whether the obstacle is that no algorithm exists or that the only algorithms are too slow; if a finite-but-astronomical procedure exists, this is the complexity prime's territory, not computability's, and the engineering responses are entirely different.

T2 — The Boundary versus Its Internal Texture (scalar). "Uncomputable" is binary on the whole partition, but the unsolvable region is itself ordered into Turing degrees and the arithmetical hierarchy — some problems are strictly harder than others above the line. The failure mode is collapsing all impossibility into one undifferentiated "can't be done," missing that an oracle for one undecidable problem may or may not decide another. Diagnostic: ask whether, granted a solver for problem X, problem Y becomes decidable; if the reduction does not go through, the two sit at different degrees and conflating them mis-estimates what escalation to an oracle would actually buy.

T3 — Worst-Case Universality versus Restricted Inputs (scopal). The undecidability verdict quantifies over all instances; restrict the input class and the same question often becomes decidable (static analysis works on practical programs though not all programs). The failure mode is the universality trap: citing the in-principle impossibility to declare a practically-restricted version hopeless, abandoning a tool that would work on the inputs that actually occur. Diagnostic: ask whether the real instance set is the full general class or a constrained subset; if the latter, the global impossibility result may not bind, and the restrict-the-inputs workaround is on the table rather than excluded.

T4 — Total Decision versus Accepted Partiality (sign/completeness). The dream is a total decider, correct on every input; the achievable is semi-decision — correct when it halts, but possibly silent. The failure mode is demanding totality where only partiality is available, rejecting a sound-but-incomplete analyzer as "buggy" because it produces false positives, when those are the unavoidable price of staying on the decidable side. Diagnostic: ask whether the tool's gaps are defects to fix or the structural cost of an in-principle boundary; if no total decider can exist, the soundness/completeness trade-off is a posture to choose deliberately, not a quality problem to eliminate.

T5 — Self-Reference as Engine versus as Trap (reflexivity). Diagonalization manufactures undecidability by feeding a procedure its own description — the engine of every impossibility proof — but the same reflexive move is a live structural hazard in the systems being reasoned about: an auditor auditing itself, a clause prohibiting its own amendment. The failure mode is designing a procedure that must decide general properties of its own outputs and not recognizing it has built a halting-shaped problem into itself. Diagnostic: ask what the procedure says when applied to its own description; if self-application can be made to contradict the procedure's verdict, an in-principle limit is wired into the design.

T6 — Model-Invariance versus Artifact-of-Rules (frame). The Church–Turing thesis says the line survives every reasonable change of formalism, which tempts the analyst to read every encountered limit as fundamental. But in non-computational substrates (a regulator unable to rule, a clinician facing an ill-posed question) the obstruction may be a fundamental under-determination or merely an artifact of the current rules a procedural change would dissolve. The failure mode is treating a fixable institutional gap as a Gödelian wall, or vice versa. Diagnostic: ask whether changing the rule-set could resolve the question; if a procedural amendment settles it, the limit was an artifact, not an in-principle boundary.

Structural–Framed Character

Computability sits at the structural pole of the structural–framed spectrum: a medium-neutral boundary claim about which problem classes admit an effective procedure, carrying a zero aggregate with every diagnostic reading structural.

The pattern carries no home vocabulary that must travel with it: although it was born in the theory of computation, the boundary is told in a logician's Entscheidungsproblem, a physicist's spectral-gap undecidability, a linguist's parsing intractability, and an institutional analyst's "no procedure within the current rules settles this," each in its own field's words — the Turing-machine formalism is one of a dozen interchangeable models the Church–Turing thesis unifies, not a lexicon that must ride along. It carries no evaluative weight: that a problem is uncomputable is neither good nor bad, merely a structural fact that re-orients the response from "try harder" to restrict / accept-partial / escalate. Its origin is formal — a partition between a question class and a procedure class, established by diagonalization and reduction, with no appeal to human norms. It is not bound to a human practice: the halting-problem contradiction is a property of the problem, not of any solver's ingenuity or institution, and the spectral-gap result holds of quantum lattice models indifferent to whether anyone is asking. And invoking it recognizes a boundary already present in the structure — the diagonal argument exposes a line wired into any sufficiently expressive procedural system — rather than importing an interpretive frame; the law-and-governance "analogue" in the entry is explicitly flagged as analogical precisely because the genuine prime is the formal boundary, and institutions only inherit its shape. Every diagnostic points one way, which is why the grade is a clean structural zero.

Substrate Independence

Computability is about as substrate-independent as a prime can be — composite 5 / 5 on the substrate-independence scale. Its signature is a medium-neutral boundary claim — fix a class of well-posed questions and a class of effective procedures, and ask whether some instance lies on the unanswerable side — and that claim makes no commitment to any particular machine, formalism, or medium, which is exactly what the Church–Turing thesis certifies when it shows the line surviving every change from Turing machines to the λ-calculus to μ-recursive functions. Because the boundary is a property of the problem rather than the apparatus, it is recognized rather than translated when it surfaces in a new field, and it surfaces almost everywhere: the halting problem and Hilbert's tenth in mathematics, Rice's theorem and undecidable type systems in computer science, the parsing of unrestricted grammars in linguistics, the spectral-gap undecidability of quantum lattice models in physics, uncomputable equilibria in economics, undecidable property-checking in AI verification, and — flagged as analogical — the institutional "no procedure within the current rules settles this" of law and governance. The abstraction is maximal: the structural engine (diagonalization, reduction, the restrict / accept-partial / escalate triad) is stated in terms of questions and procedures with no domain-specific commitments. And the transfer is heavily documented, with the same self-reference move running through Cantor, Gödel, Turing, and Tarski and the same impossibility-by-reduction technique porting into impossibility arguments far from computing. Maximal breadth, maximal abstraction, and well-documented transfer all line up at the ceiling.

• Composite substrate independence — 5 / 5
• Domain breadth — 5 / 5
• Structural abstraction — 5 / 5
• Transfer evidence — 5 / 5

Relationships to Other Abstractions

Current abstraction Computability Prime

Parents (1) — more general patterns this builds on

• Computability presupposes Algorithm Prime

  Per dossier and file: computability is 'the boundary/meta-level relation that algorithm presupposes' — the existence-question (does an effective procedure exist at all?) over algorithm's central object.

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

• Blum–Shub–Smale Machine Domain-specific is a kind of Computability

  Computability is the strict parent by composition.

• Computable real function Domain-specific is a kind of Computability

  The proposed strict upward parent is prime:computability.

• Enumeration reducibility Domain-specific is a kind of Computability

  The proposed strict upward parent is prime:computability.

▸ Show 4 more

Hierarchy paths (2) — routes to 2 parentless roots

• Computability → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space

Computability sits among the more crowded primes in the catalog (38^th percentile for distinctiveness): several abstractions describe nearly the same structure, so a description that fits it will tend to fit its neighbors too — transporting it usually means disambiguating within this family rather than landing on it exactly.

Family — Formal Systems & Structural Conditions (20 primes)

Nearest neighbors

• Decidability Computability — 0.79
• Algorithm — 0.75
• Containerization — 0.71
• Embeddability — 0.71
• Constraint — 0.70

Computed from structural-signature embeddings · 2026-09-10

Not to Be Confused With

The most consequential confusion is between computability and complexity (and its resource-explicit form complexity_time_space), because both speak of what procedures can do with problems, and casual usage blurs "impossible" with "intractable." The distinction is sharp and load-bearing. Complexity assumes a problem is solvable — an algorithm exists — and asks how its resource demand scales: polynomial versus exponential, feasible versus infeasible within a budget. Computability asks the prior question of whether any procedure exists at all, with resources unbounded. A problem can be computable but require time exponential in the input (NP-hard problems are decidable; you can always brute-force them given enough time), and a problem can be uncomputable so that no finite or infinite resource budget helps (the halting problem admits no decider however slow). The practical stakes are entirely different: against a complexity wall the responses are approximation, heuristics, special-case structure, or more compute; against a computability wall those moves are futile, and the only responses are to restrict the inputs, accept partiality, or escalate to an oracle. Mislabeling one as the other wastes effort — either abandoning a tractable search as "impossible" or grinding compute against a problem that no machine can decide.

A second confusion is with algorithm, and it turns on the procedure–problem asymmetry that the Core Idea emphasizes. An algorithm is a positive, exhibitable object: a finite recipe you can write down, run, and inspect. Computability is a property of a problem class — whether such an object can exist — and on its negative side it is established not by exhibiting anything but by proving non-existence via diagonalization or reduction. The two are related as a thing to the question of whether that thing is buildable, and they fail to be interchangeable in a revealing way: one can have a rich computability theory (the whole hierarchy of Turing degrees) about problems for which no algorithm exists, and one can have an algorithm without ever raising the computability question (most working code). Conflating them produces the error of thinking that failing to find an algorithm is evidence of uncomputability — when "I could not construct one" is categorically weaker than "no procedure of any kind exists," the latter requiring a proof.

Computability is also distinct from decidability_computability, with which it overlaps so heavily that the same diagonal arguments power both. Decidability strengthens computability to a total, two-sided guarantee — a procedure that halts on every instance with the correct yes/no — and its logic-side framing is the special case in which the "question class" is the validity, satisfiability, or provability of formulas in a particular formal system and the "procedure class" is mechanical proof-search or model-checking. Computability is the general medium-neutral boundary, of which decidability is one instance — the Entscheidungsproblem is the computability question asked about first-order logic specifically. The reason to keep them separate is that the substrate differs: decidability-in-logic carries commitments about syntax, axioms, and a deductive apparatus, while computability abstracts away from any particular logic to "a class of well-posed questions and a class of effective procedures." A linguistic-parsing undecidability, a spectral-gap undecidability in physics, and a Diophantine-solvability undecidability are all computability results but only the logical ones are decidability-of-a-logic results.

For a practitioner the cluster sorts cleanly once the diagnostic questions are kept in order. First ask whether any procedure exists — if not, it is a computability boundary and only the restrict/accept-partial/escalate triad applies. If a procedure does exist, ask whether it is affordable — if not, it is a complexity problem and approximation or special-case structure are on the table. Only when a concrete recipe is in hand is one in the territory of algorithm proper. Folding these three questions into one undifferentiated "can it be done?" is the source of nearly every misdiagnosis in the cluster, because each layer has an entirely different repertoire of legitimate responses.

Solution Archetypes

Solution archetypes in the catalog that build on this prime — directly (this prime is a source ingredient) or as a related prime.

Built directly on this prime (2)

• Computability Boundary Mapping: Before optimizing or automating a problem, determine whether any correct terminating procedure can solve the declared class, prove that boundary, and publish a weaker but honest fallback when it cannot.
  ▸ Mechanisms (18)
• Decision-Procedure Boundary Mapping: Map whether a yes/no question can be decided by a finite total procedure before promising automation, certainty, or universal adjudication.
  ▸ Mechanisms (5)

Also a related prime in 2 archetypes

• Bounded-Rationality Decision Design: Match decision method, search depth, sufficiency threshold, and escalation to the real limits and stakes of the choice.
• Dispute-Question Alignment: Stop arguing over answers until the parties have identified which kind of question they are actually contesting.

References

[1] Turing, Alan M. "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society, ser. 2, vol. 42 (1936): 230–265. Defines the Turing machine, proves the halting problem undecidable by diagonalization, and (with Church) grounds the Church–Turing thesis that the computable functions are model-invariant. registry ↩a ↩b

[2] Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems". Transactions of the American Mathematical Society, vol. 74, no. 2 (1953): 358–366. Rice's theorem: no algorithm decides any non-trivial semantic property of arbitrary programs, the in-principle boundary behind static-analysis limits. registry ↩a ↩b

[3] Cantor, Georg. "Über eine elementare Frage der Mannigfaltigkeitslehre". Jahresbericht der Deutschen Mathematiker-Vereinigung, vol. 1 (1891): 75–78. Introduces the diagonal argument, the self-reference engine reused by Gödel, Turing, and Tarski. registry ↩a ↩b

[4] Post, Emil L. "Recursively Enumerable Sets of Positive Integers and Their Decision Problems". Bulletin of the American Mathematical Society, vol. 50, no. 5 (1944): 284–316. Initiates the theory of degrees of unsolvability (Turing degrees), giving the unsolvable region internal structure ordered by relative computability. registry ↩

[5] Gödel, Kurt. "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I". Monatshefte für Mathematik und Physik, vol. 38 (1931): 173–198. The incompleteness theorems, a sibling result driven by the same self-reference/diagonalization engine as undecidability. registry ↩

[6] Wells, J. B. "Typability and Type Checking in the Second-Order Lambda-Calculus Are Equivalent and Undecidable". Proceedings of the 9^th Annual IEEE Symposium on Logic in Computer Science (LICS) (1994): 176–185. Proves type inference for System F (second-order lambda calculus) undecidable, an instance of undecidable type systems. registry ↩

[7] Hopcroft, John E., and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley, 1979. Establishes that type-0 (unrestricted) phrase-structure grammars generate exactly the recursively enumerable languages and that their membership/recognition problem is undecidable — a structural reason general grammar parsing must use constrained classes. registry ↩

[8] Cubitt, Toby S., David Pérez-García, and Michael M. Wolf. "Undecidability of the Spectral Gap". Nature, vol. 528, no. 7581 (2015): 207–211. Proves that whether certain translation-invariant quantum lattice models are gapped is undecidable. registry ↩

[9] Spear, Stephen E. "Learning Rational Expectations under Computability Constraints". Econometrica, vol. 57, no. 4 (1989): 889–910. Shows that when equilibrium price functions are required to be computable, a version of Gödel's incompleteness theorem implies rational-expectations equilibria cannot in general be learned — establishing that procedurally computable equilibria are bounded by computability constraints and some are uncomputable. registry ↩