Computability

Computability is the branch of the theory of computation that asks which problems can be solved by a mechanical procedure at all — not quickly, not with a given amount of memory, but in principle, given unlimited time and resources.

15 frameworks, from 1932 to today · Theory Of Computation · Computer Science

still a working view ended · each leads to its entry below

Overview

Computability is the branch of the theory of computation that asks which problems can be solved by a mechanical procedure at all — not quickly, not with a given amount of memory, but in principle, given unlimited time and resources123. Its central discovery is negative and permanent: there are well-defined problems no algorithm can ever solve, and there are more of them than there are solvable ones. Every programming language, every computer, and every future machine is bounded by these results. The field grew out of a foundational crisis in mathematics, was rebuilt as a theory of abstract machines and functions, and then expanded into a rich landscape of degrees of unsolvability, relative computability, randomness, and the reverse-mathematical analysis of ordinary mathematics.

Hilbert's Program and the Decision Problem

In 1928 David Hilbert and Wilhelm Ackermann posed the Entscheidungsproblem: is there a mechanical procedure that decides, for any statement in first-order logic, whether it is valid45? The question presupposed a precise notion of "mechanical procedure," which did not yet exist. Hilbert's broader program hoped to secure all of mathematics by finitary consistency proofs, and a positive answer to the decision problem would have been a major prize. The 1931 incompleteness theorems of Kurt Gödel showed that any sufficiently strong, consistent, effectively axiomatized theory is incomplete — a first sign that the boundary between the mechanical and the non-mechanical was itself mathematically tractable6.

The 1930s: Three Models of Computability

The decisive decade produced several independent formalizations of "effective procedure," and their convergence became the field's founding fact.

Gödel, building on work of Jacques Herbrand, introduced the recursive functions in 1934: the primitive recursive functions (built from zero, successor, and projection by composition and recursion) plus the μ-operator, which searches for the least input making a function zero. A function is general recursive if it can be defined this way7. This "recursive function theory" gave a purely arithmetical notion of computability, and it remains the standard vocabulary of the field.

Alonzo Church developed the lambda calculus in the early 1930s: a calculus of functions built from variables, application, and abstraction, with conversion rules for substituting arguments48. It was a universal language for defining functions — Church's student Stephen Kleene used it to prove that not all functions are λ-definable — but it was initially a tool of mathematical logic rather than a model of a machine.

Alan Turing's 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem supplied the model that stuck491011. A Turing machine is an abstract device with a finite set of states, a tape divided into cells, and a head that reads and writes symbols and moves left or right according to a fixed table of rules9. Turing defined a number as computable if some such machine, starting on a blank tape, prints its decimal expansion. The model was deliberately minimal, and its power came from that: anything a human "computer" could do by following a finite rulebook, a Turing machine could do.

Turing then proved the undecidability of the halting problem: no Turing machine can decide, given a description of an arbitrary machine and its input, whether that machine eventually halts12. The proof is a diagonal argument — assume a decider exists, feed it a modified copy of itself, and derive a contradiction. Church reached the same conclusion for the Entscheidungsproblem through the lambda calculus, and Emil Post, working independently, arrived at a similar analysis of "finite combinatory processes." The convergence of these independent routes is the evidence behind the Church–Turing thesis: the informal notion of an effectively computable function coincides with the formally defined one4. The thesis is not a theorem but a claim about the adequacy of a definition, and no counterexample has survived.

Reductions, Enumerability, and the Arithmetical Hierarchy

Once undecidability was established, the natural next question was how undecidable problems relate to one another. Turing introduced oracle computability: a machine with access to an oracle for a set A can query membership in A as a primitive step11314. This relativizes computability and lets one compare problems by Turing reduction — B is computable from A if a machine with an A-oracle decides B13. A weaker notion, many-one reduction, maps instances of one problem to another by a computable function15.

The recursively enumerable (r.e.) sets — those whose members can be listed by some machine, equivalently those that are the domain of a partial computable function — became a central object16. A set is r.e. but not computable exactly when it is undecidable yet semi-decidable: the halting set is the paradigm1. Post's problem, posed in 1944, asked whether there is an r.e. set strictly between the computable sets and the halting set under Turing reduction; it drove the field for a decade.

Kleene's work in the 1940s and 1950s organized these notions into the arithmetical hierarchy. A set is Σ₁ if it is r.e., Π₁ if its complement is r.e., Σ₂ if it is r.e. relative to the halting set, and so on; each level is defined by the number of alternating quantifiers in an arithmetical definition17. The hierarchy measures how far a problem sits from decidability, and it made precise the intuition that some undecidable problems are "harder" than others.

Degrees and the Priority Method

Turing degree theory studies the equivalence classes of sets under mutual Turing reducibility18. The degrees form a partial order with a least element (the computable sets) and no greatest element. The central construction of the 1950s was the priority method, invented independently by Albert Muchnik and Richard Friedberg in 1956–57 to solve Post's problem: they built an r.e. set whose degree is strictly between the computable and halting degrees. The method works by listing infinitely many requirements that a construction must satisfy and giving them a priority order, so that a requirement, once satisfied, is never injured by lower-priority ones — or is injured only finitely often18. It became the field's workhorse, later refined into the finite-injury and infinite-injury techniques used to build degrees with prescribed properties.

Gerald Sacks, Stephen Kleene, and Emil Post himself shaped the resulting structure theory: the r.e. degrees are dense, the jump operator (which maps a set to its halting problem) stratifies them, and the global degree structure is enormously complex. Higher computability theory extends these notions to admissible sets and to ordinals beyond the natural numbers, asking what "computable" means when the underlying domain is uncountable or transfinite; it connects computability to set theory and definability.

Diophantine Problems and the MRDP Theorem

A striking application came from number theory. In 1900 Hilbert asked for an algorithm deciding whether a Diophantine equation — a polynomial equation with integer coefficients — has integer solutions19. Work by Martin Davis, Hilary Putnam, and Julia Robinson in the 1950s and 1960s reduced the problem to showing that every r.e. set is Diophantine. Yuri Matiyasevich completed the proof in 1970, giving the MRDP theorem: every r.e. set is the set of solutions of some Diophantine equation1920. The consequence is that Hilbert's tenth problem is undecidable — no algorithm decides Diophantine solvability in general19. The theorem also yields a concrete universal Diophantine equation whose solvability encodes the halting problem, making undecidability tangible in ordinary arithmetic.

Algorithmic Randomness

In the 1960s and after, computability theory turned to the question of what it means for a finite string or infinite sequence to be random. The intuition is that a random string has no short description: its Kolmogorov complexity — the length of the shortest program that outputs it — is close to its own length. Andrei Kolmogorov, Ray Solomonoff, and Gregory Chaitin developed this theory independently. Per Martin-Löf gave a measure-theoretic definition of randomness in 1966: a sequence is random if it passes every effective statistical test. Later work by Claus-Peter Schnorr, Leonid Levin, and others connected randomness to martingales and to computational hardness, and the field now studies a hierarchy of randomness notions (Martin-Löf, Schnorr, Kurtz, and others) that measure how much computational power a test is allowed.

Reverse Mathematics and Computable Model Theory

Two further branches asked what computability does for ordinary mathematics. Reverse mathematics, founded by Harvey Friedman and developed systematically by Stephen Simpson from the 1970s, asks which set-existence axioms are needed to prove theorems of classical analysis, algebra, and combinatorics. The program identified a small number of subsystems of second-order arithmetic — RCA₀, WKL₀, ACA₀, ATR₀, Π¹₁-CA₀ — and showed that most theorems of ordinary mathematics are equivalent, over a weak base theory, to one of them. The base system RCA₀ restricts comprehension to computable sets, so the whole program is computability theory applied to proof strength.

Computable model theory applies computability to the structures studied in model theory: a countable structure is computable if its domain and operations can be represented so that equality and the basic relations are decidable. The field asks which classical theorems survive when structures are restricted to computable ones, and it produced notions such as computable categoricity and the degrees of presentations of a structure.

The Present

Computability theory today is a mature field with several active fronts. Classical degree theory continues, with work on the global structure of the Turing degrees and on definability. Algorithmic randomness and Kolmogorov complexity have grown into a large area with connections to information theory, proof complexity, and the analysis of learning. Reverse mathematics remains productive, with ongoing calibration of theorems from analysis, combinatorics, and even parts of physics. Higher computability and the computability of uncountable structures connect the field to set theory and descriptive set theory. The Church–Turing thesis itself is no longer contested as a working hypothesis, but its precise status — and the question of which physical or mathematical processes might compute more than Turing machines — remains a live philosophical and technical question. What unites the field is the same question Turing asked in 1936: what does it mean for a procedure to be mechanical, and what follows from that definition?

References

  1. Computability (introduction, Oracle machines, Beyond recursively enumerable languages), Wikipedia
  2. Theory of computation, Wikipedia
  3. Computational complexity theory, Wikipedia
  4. Church–Turing thesis (History, introduction), Wikipedia
  5. Entscheidungsproblem (introduction, History), Wikipedia
  6. Gödel's incompleteness theorems, Wikipedia
  7. General recursive function, Wikipedia
  8. Lambda calculus (introduction, History), Wikipedia
  9. Turing machine, Wikipedia
  10. Universal Turing machine, Wikipedia
  11. Turing's proof, Wikipedia
  12. Halting problem (introduction, Background), Wikipedia
  13. Turing reduction, Wikipedia
  14. Oracle machine, Wikipedia
  15. Many-one reduction, Wikipedia
  16. Computably enumerable set, Wikipedia
  17. Post's theorem (Background), Wikipedia
  18. Turing degree (introduction, Post's problem and the priority method), Wikipedia
  19. Hilbert's tenth problem, Wikipedia
  20. Diophantine set (Matiyasevich's theorem), Wikipedia

The frameworks of Computability

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1932-Present

    Lambda Calculus

    What functions can be defined purely by abstraction and application?

    Fly to its tower in Nousfarer

  2. 1934-Present

    General recursive function

    Which functions can be computed from basic arithmetic operations?

    Fly to its tower in Nousfarer

  3. 1936-Present

    Church–Turing thesis

    Does one formal definition capture all mechanical computation?

    Fly to its tower in Nousfarer

  4. 1936-Present

    Turing machine

    What can a machine with a finite rulebook compute?

    Fly to its tower in Nousfarer

  5. 1936-Present

    Undecidability and reduction

    Which problems can no algorithm ever solve?

    Fly to its tower in Nousfarer

  6. 1939-Present

    Oracle Computability and Reducibility

    What can be computed given answers to another problem?

    Fly to its tower in Nousfarer

  7. 1944-Present

    Arithmetical hierarchy

    How hard is an undecidable problem compared to others?

    Fly to its tower in Nousfarer

  8. 1944-Present

    Recursively enumerable set theory

    Which sets can a machine list out completely?

    Fly to its tower in Nousfarer

  9. 1954-Present

    Turing degree

    How do unsolvable problems rank against one another?

    Fly to its tower in Nousfarer

  10. 1956-Present

    Priority Method

    How can we construct a set with a prescribed degree?

    Fly to its tower in Nousfarer

  11. 1960-Present

    Higher Computability Theory

    What does computability mean beyond the natural numbers?

    Fly to its tower in Nousfarer

  12. 1966-Present
  13. 1970-Present

    Computable Model Theory

    Which mathematical structures have computable presentations?

    Fly to its tower in Nousfarer

  14. 1970-Present

    Diophantine Representation (MRDP)

    Is there an algorithm deciding integer polynomial equations?

    Fly to its tower in Nousfarer

  15. 1975-Present

    Reverse Mathematics

    Which axioms are needed to prove ordinary theorems?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Lambda CalculusGeneral recursive functionChurch–Turing thesisTuring machineUndecidability and reductionOracle Computability and ReducibilityArithmetical hierarchyRecursively enumerable set theoryTuring degreePriority MethodHigher Computability TheoryAlgorithmic Randomness and Kolmogorov…Computable Model TheoryDiophantine Representation (MRDP)Reverse Mathematics

Beyond the field

Where Computability's ideas came from in other fields, and what they led to there: the strongest 12 of 83 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Computability is a planet in Nousfarer

Its city has a tower for each of these 15 frameworks. Land, walk in, and climb one concept at a time.

Land on Computability

Related fields

Fields its ideas are linked to

More in Theory Of Computation

See where Computability sits on the Map of Human Knowledge