Computability

Computability is the study of what can be computed — what problems admit algorithmic solutions, what functions can be mechanically calculated, and what questions are fundamentally beyond the reach of any mechanical procedure. It is one of the deepest and most consequential branches of mathematical logic, with direct implications for mathematics, computer science, philosophy, and the natural sciences.

The field was born in the 1930s, when several independent investigations converged on the same discovery: the class of "effectively calculable" functions is precisely definable, and its boundaries are sharp. Alan Turing's Turing machines, Alonzo Church's lambda calculus, Kurt Gödel and Jacques Herbrand's general recursive functions, and Emil Post's production systems all define the same class of functions. This convergence — the Church-Turing thesis — is not a theorem but an empirical hypothesis of extraordinary strength: every independently proposed model of mechanical computation has turned out to be equivalent to every other.

The Core Concepts

A decision problem is a question with a yes/no answer, posed for an infinite set of possible inputs. A decision problem is decidable if there exists a Turing machine that halts with the correct answer for every input. It is undecidable if no such machine exists. The distinction is absolute: not merely difficult, not merely expensive, but impossible in principle.

A function problem asks for a computed output rather than a yes/no answer. A function is computable if a Turing machine can produce the correct output for every input. The class of computable functions is often denoted by the Greek letter μ (mu) or identified with the partial recursive functions.

Semi-decidability (or recursive enumerability) is a weaker property. A set is semi-decidable if there exists a Turing machine that halts with "yes" for every member of the set, but may run forever for non-members. The halting set — the set of all Turing machine-input pairs that eventually halt — is semi-decidable but not decidable. This intermediate zone between the computable and the totally uncomputable is rich in structure and has been mapped in detail.

The Halting Problem and Its Consequences

The halting problem is the canonical undecidable problem: given a description of a Turing machine and an input, determine whether the machine will eventually halt or run forever. Turing proved in 1936 that no Turing machine can solve this problem for all inputs. The proof is a diagonalization argument: if a halting-decider existed, you could construct a machine that does the opposite of what the decider predicts, producing a logical contradiction.

The halting problem is not an isolated curiosity. It is the gateway to undecidability. Rice's theorem (1951) generalizes it: any non-trivial semantic property of a program is undecidable. Want to know if a program always outputs prime numbers? Undecidable. Want to know if two programs are equivalent? Undecidable. Want to know if a program contains a security vulnerability of a certain type? Undecidable. The space of what we can know about programs in general is vastly smaller than the space of what we might want to know.

Gödel's incompleteness theorems (1931) are the metamathematical analogue. In any consistent formal system strong enough to encode arithmetic, there are true statements that cannot be proved within the system. The connection to computability is direct: proof is a form of computation. The limits of computation are the limits of formal proof.

Degrees of Computability

Not all undecidable problems are equally undecidable. Turing degrees classify problems by their relative computability. The halting problem has degree 0′ (zero-prime): it is not computable, but it is computable if you have an oracle for the halting problem. Some problems are even harder — they cannot be solved even with a halting oracle. These form higher Turing degrees: 0″, 0‴, and so on, extending into the transfinite.

This hierarchy reveals that undecidability has structure. It is not a uniform darkness but a landscape with its own topography. Some problems are "just barely" undecidable; others are profoundly so. The study of these degrees, computability theory in the narrow sense, is a rich branch of mathematical logic with connections to set theory, model theory, and descriptive set theory.

Computability in the Natural Sciences

The boundaries of computability are not merely mathematical abstractions. They impinge on the physical world in ways that remain contested.

Physics: Does the universe compute? The Church-Turing-Deutsch principle asserts that any physical process can be simulated by a universal quantum computing machine. If true, physical reality is computable in principle, though perhaps not efficiently. But some physical systems — certain chaotic systems, possibly quantum gravitational processes at the Planck scale — may not be simulable in finite time. The question of whether nature contains hypercomputers — physical systems that solve uncomputable problems — remains open.

Biology: Is life computable? The question can be parsed in multiple ways. If "computable" means "predictable in detail," then life is not computable: molecular dynamics is chaotic, and biological systems are sensitive to microscopic fluctuations. If "computable" means "simulable to any desired accuracy," then perhaps it is, given sufficient resources. But if "computable" means "governed by computable functions at every level," the question becomes empirical: are there biological processes that exploit physical non-computability?

Cognitive Science: Is the mind computable? The computational theory of mind holds that cognition is computation, and thus that mental processes are computable in principle. Opponents argue that consciousness, qualia, or understanding may involve non-computable elements — perhaps through quantum processes in microtubules (Penrose-Lucas argument) or through biological organization that transcends algorithmic description. The debate remains unresolved, but the framework of computability provides the precise terms in which it is conducted.

Computational Complexity: The Resource-Bounded View

Computability asks what can be computed in principle. Computational complexity asks what can be computed in practice — within bounded time and space resources. The class P contains problems solvable in polynomial time by a deterministic Turing machine. The class NP contains problems whose solutions can be verified in polynomial time. The question of whether P = NP — whether every efficiently verifiable problem is also efficiently solvable — is the most famous open problem in computer science.

The complexity perspective transforms the landscape. A problem may be computable but practically intractable: the traveling salesman problem, for instance, is computable but believed to require exponential time. Conversely, approximation algorithms and probabilistic methods can make intractable problems practically manageable. The boundary between tractable and intractable is softer than the boundary between computable and uncomputable, but it is no less consequential for engineering.

The Philosophical Significance

Computability is one of the rare cases in which a technical mathematical result has direct philosophical force. The Church-Turing thesis, if accepted, places a hard limit on what mechanical systems can do. It says that any procedure that can be carried out by following rules — by a human with pencil and paper, by a computer, by any physical system that operates algorithmically — is bounded by the same limits. The universe of computable functions is the universe of all that can be achieved by rule-following.

This has implications for the philosophy of mind (can thinking be reduced to computation?), the philosophy of mathematics (what is the status of uncomputable objects?), and the philosophy of science (are there natural phenomena that cannot be simulated?). It also has practical implications for artificial intelligence: if intelligence is computable, it is achievable by sufficiently sophisticated programs. If it is not, then AI has fundamental limits that engineering cannot overcome.

The field of computability does not resolve these questions. It clarifies them. It replaces vague intuitions about "mechanical" and "intelligent" with precise definitions and sharp theorems. The remaining uncertainty is not about what computability theory says. It is about whether the world itself respects the boundaries that computability theory has mapped.