Skip to content

Computability

Version
v1 · 2026-08-24 · History
Prime #
722
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomain
Theory of Computation → Computer Science & Software Engineering
Aliases
Church Turing Thesis

Core Idea

Computability is the line — drawn by diagonalization and reduction — between problems for which an effective procedure exists and problems for which none does. The impossibility is in principle, a property of the problem itself: no increase in speed, memory, or ingenuity moves an uncomputable problem to the computable side.

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').

Broad Use

  • Mathematics and logic: the halting problem; Hilbert's tenth; Gödel's incompleteness as a sibling self-reference result.
  • Computer science: Rice's theorem — no algorithm decides non-trivial semantic properties of arbitrary programs.
  • Linguistics: parsing for unrestricted phrase-structure grammars is undecidable, a reason the field uses constrained grammar classes.
  • Physics: the spectral-gap problem for certain quantum lattice models is undecidable.
  • Economics: the existence of a procedurally computable equilibrium is bounded by computability constraints.
  • AI alignment: "does this network satisfy this property on all inputs?" is undecidable for expressive networks, so verification restricts the classes.

Clarity

Separates hard but solvable from unsolvable in principle, re-orienting the response from "try harder" to constrain the problem, accept partiality, or change the question.

Manages Complexity

Partitions all well-posed problems into two disjoint regions, so an uncomputable problem redirects effort from a doomed algorithm search into exactly three workarounds: restrict the inputs, accept partiality, or escalate to an oracle.

Abstract Reasoning

Enables reduction proofs (encode a known-unsolvable problem inside the target), diagonal arguments (apply a supposed solver to its own description), and oracle-relative reasoning.

Knowledge Transfer

  • Institutional review: the diagonal "what does the auditing rule say about auditing itself?" is recognizably the same self-reference move.
  • Policy and design: "if you could solve X you could solve the known-impossible Y" is the structural analogue of a computability reduction.
  • Engineering posture: every analysis-tool team (linters, scanners, model checkers) implicitly chooses one of the restrict / accept-partial / escalate workarounds.

Example

Turing's halting proof assumes a decider \(H\), builds a program \(D\) that does the opposite of what \(H\) predicts about it, and applies \(D\) to its own description — a contradiction — so no \(H\) exists, and no faster machine ever changes that.

Relationships to Other Abstractions

Local relationship map for 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.ComputabilityPRIMEPrime abstraction: Algorithm — presupposesAlgorithmPRIMEDomain-specific abstraction: S-m-n Theorem — presupposesS-m-n TheoremDOMAINDomain-specific abstraction: Blum–Shub–Smale Machine — is a kind ofBlum–Shub–SmaleMachineDOMAINDomain-specific abstraction: Computable real function — is a kind ofComputablereal functionDOMAINDomain-specific abstraction: Enumeration reducibility — is a kind ofEnumerationreducibilityDOMAINDomain-specific abstraction: General recursive function — is a kind ofGeneral recursi…DOMAINDomain-specific abstraction: Reduction (Computability Theory) — is a kind ofReduction (Comp…DOMAINPrime abstraction: Decidability Computability — is a kind of, typicalDecidabilityComputabilityPRIME

Current abstraction Computability Prime

Parents (1) — outgoing typed relations

  • 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) — abstractions linked here by typed relations

  • 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

    It remains its own entry because its identity is fixed by the represented real domain and codomain, input and output naming systems, algorithm or machine model, requested precision, convergence guarantee, continuity modulus and partial-domain and uniformity conventions.

  • Enumeration reducibility Domain-specific is a kind of Computability

    What makes it its own entry: the domain-specific identity determined by one uniform effective operator maps every enumeration of B to an enumeration of A using only finite positive information.

  • General recursive function Domain-specific is a kind of Computability

    It remains its own entry because its identity is fixed by the arity and natural-number domain, initial functions, construction clauses, composition and primitive-recursion steps, minimization predicate and convergence, partiality or totality and equivalence with a machine model.

  • Reduction (Computability Theory) Domain-specific is a kind of Computability

    Computability is the broader abstraction this entry instantiates.

Hierarchy path (1) — routes to 1 parentless root

Not to Be Confused With

  • Computability is not Complexity because computability asks whether any procedure exists regardless of cost, whereas complexity asks how expensive an already-solvable problem is within a resource budget.
  • Computability is not Algorithm because an algorithm is a positive object you exhibit, whereas computability is the boundary question of whether such an object can exist at all, established on its negative side by proving non-existence.
  • Computability is not Decidability (Computability) because decidability is the special case where the question class is the validity or provability of a particular formal system, whereas computability is the general medium-neutral boundary.