- Atlas
- Computer Science
- Computability
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
- Lambda Calculus 1932-Present
- General recursive function 1934-Present
- Church–Turing thesis 1936-Present
- Turing machine 1936-Present
- Undecidability and reduction 1936-Present
- Oracle Computability and Reducibility 1939-Present
- Arithmetical hierarchy 1944-Present
- Recursively enumerable set theory 1944-Present
- Turing degree 1954-Present
- Priority Method 1956-Present
- Higher Computability Theory 1960-Present
- Algorithmic Randomness and Kolmogorov Complexity 1966-Present
- Computable Model Theory 1970-Present
- Diophantine Representation (MRDP) 1970-Present
- Reverse Mathematics 1975-Present
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
- Computability (introduction, Oracle machines, Beyond recursively enumerable languages), Wikipedia
- Theory of computation, Wikipedia
- Computational complexity theory, Wikipedia
- Church–Turing thesis (History, introduction), Wikipedia
- Entscheidungsproblem (introduction, History), Wikipedia
- Gödel's incompleteness theorems, Wikipedia
- General recursive function, Wikipedia
- Lambda calculus (introduction, History), Wikipedia
- Turing machine, Wikipedia
- Universal Turing machine, Wikipedia
- Turing's proof, Wikipedia
- Halting problem (introduction, Background), Wikipedia
- Turing reduction, Wikipedia
- Oracle machine, Wikipedia
- Many-one reduction, Wikipedia
- Computably enumerable set, Wikipedia
- Post's theorem (Background), Wikipedia
- Turing degree (introduction, Post's problem and the priority method), Wikipedia
- Hilbert's tenth problem, Wikipedia
- 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.
- 1932-Present
Lambda Calculus
What functions can be defined purely by abstraction and application?
- 1934-Present
General recursive function
Which functions can be computed from basic arithmetic operations?
- 1936-Present
Church–Turing thesis
Does one formal definition capture all mechanical computation?
- 1936-Present
- 1936-Present
Undecidability and reduction
Which problems can no algorithm ever solve?
- 1939-Present
Oracle Computability and Reducibility
What can be computed given answers to another problem?
- 1944-Present
Arithmetical hierarchy
How hard is an undecidable problem compared to others?
- 1944-Present
Recursively enumerable set theory
Which sets can a machine list out completely?
- 1954-Present
- 1956-Present
- 1960-Present
Higher Computability Theory
What does computability mean beyond the natural numbers?
- 1966-Present
Algorithmic Randomness and Kolmogorov Complexity
When is a string genuinely random?
- 1970-Present
Computable Model Theory
Which mathematical structures have computable presentations?
- 1970-Present
Diophantine Representation (MRDP)
Is there an algorithm deciding integer polynomial equations?
- 1975-Present
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.
Church–Turing thesis influenced by Turing machine
Turing's analysis of what a human computer can do by following a finite rulebook, formalized as the Turing machine, supplied the central argument for the thesis that Turing-computability equals effective computability.
Carried by Alan Turing; On Computable Numbers (1936).
Undecidability and reduction grew out of Turing machine
Turing's diagonal argument against a halting decider, built directly on the Turing machine model, established undecidability and the reduction technique used throughout the field.
Carried by Alan Turing.
Oracle Computability and Reducibility grew out of Turing machine
Turing relativized his machine model by adding an oracle, defining computability relative to an arbitrary set and yielding Turing reducibility.
Carried by Alan Turing.
Turing degree grew out of Oracle Computability and Reducibility
Turing degree theory studies equivalence classes under mutual Turing reducibility, directly refining Turing's oracle reducibility into a structure of unsolvability.
Carried by Stephen Kleene; Emil Post.
Priority Method influenced by Recursively enumerable set theory
The priority method was invented by Friedberg and Muchnik specifically to solve Post's problem by constructing an r.e. set of intermediate degree.
Carried by Richard Friedberg; Albert Muchnik.
Diophantine Representation (MRDP) influenced by Recursively enumerable set theory
The Davis–Putnam–Robinson program reduced the Diophantine problem to showing every r.e. set is Diophantine, completed by Matiyasevich in 1970.
Carried by Martin Davis; Hilary Putnam; Julia Robinson.
General recursive function rival of Lambda Calculus
Church's lambda calculus and Gödel's general recursive functions were independent, competing formalizations of effective calculability in the early 1930s; Kleene proved them equivalent in 1936, after which they were seen as the same class.
Carried by Alonzo Church; Kurt Gödel; Stephen Kleene.
Church–Turing thesis influenced by Lambda Calculus
Church used the lambda calculus to prove the Entscheidungsproblem undecidable and to argue that lambda-definability captures effective calculability, a route that fed directly into the Church–Turing thesis.
Carried by Alonzo Church.
Church–Turing thesis influenced by General recursive function
The equivalence of general recursive functions with lambda-definable and Turing-computable functions supplied the converging evidence behind the thesis that these formal notions capture effective computability.
Carried by Stephen Kleene; Alan Turing.
Algorithmic Randomness and Kolmogorov Complexity influenced by General recursive function
Kolmogorov complexity measures the length of the shortest program computing a string, using the recursive-function notion of effective description that underpinned computability theory.
Carried by Andrei Kolmogorov; Gregory Chaitin.
Computable Model Theory grew out of General recursive function
Computable model theory applies the recursive-function notion of effective construction to models and their presentations.
Recursively enumerable set theory influenced by Undecidability and reduction
The discovery of undecidable but semi-decidable sets like the halting set led Post to isolate the recursively enumerable sets and pose his problem about their degrees.
Carried by Emil Post.
Algorithmic Randomness and Kolmogorov Complexity influenced by Undecidability and reduction
Algorithmic randomness defines randomness via effective tests and incompressibility, concepts that presuppose undecidability and the limits of mechanical description.
Carried by Per Martin-Löf; Andrei Kolmogorov.
Diophantine Representation (MRDP) influenced by Undecidability and reduction
The MRDP theorem showed every r.e. set is Diophantine, turning Hilbert's tenth problem into an undecidability result in the tradition of the halting problem.
Carried by Martin Davis; Hilary Putnam; Julia Robinson.
Arithmetical hierarchy grew out of Oracle Computability and Reducibility
Kleene built the arithmetical hierarchy by iterating the halting-set jump and relativizing computability to oracles, organizing sets by alternating quantifiers.
Carried by Stephen Kleene.
Recursively enumerable set theory influenced by Oracle Computability and Reducibility
Post's formulation of r.e. sets and his problem were posed in terms of Turing reducibility, the oracle-based relation Turing had introduced.
Carried by Emil Post.
Higher Computability Theory grew out of Arithmetical hierarchy
Higher computability theory generalized the arithmetical hierarchy and jump to admissible sets and transfinite ordinals, extending Kleene's definability approach beyond arithmetic.
Carried by Stephen Kleene; Gerald Sacks.
Reverse Mathematics influenced by Arithmetical hierarchy
Reverse mathematics measures the strength of ordinary mathematical theorems over weak base theories, calibrated by the arithmetical and definability hierarchies.
Carried by Harvey Friedman; Stephen Simpson.
Higher Computability Theory grew out of Turing degree
Higher computability extended Turing degree theory to admissible sets and ordinals, asking what degrees and jumps mean in transfinite settings.
Carried by Gerald Sacks.
Reverse Mathematics influenced by Recursively enumerable set theory
Reverse mathematics grew out of the study of effective and recursively enumerable set existence principles underlying ordinary mathematics.
Carried by Harvey Friedman; Stephen Simpson.
Algorithmic Randomness and Kolmogorov Complexity influenced by Turing degree
Later work connected randomness notions to computational hardness and relative computability, drawing on the degree-theoretic tradition.
Carried by Leonid Levin; Claus-Peter Schnorr.
Computable Model Theory influenced by Priority Method
Priority constructions became a standard tool for building computable and non-computable presentations of models with prescribed degree properties.
Beyond the field
Where Computability's ideas came from in other fields, and what they led to there: the strongest 12 of 83 links.
Lambda Calculus led to System F in Type Theory
System F is a typed extension of Church's lambda calculus, whose untyped form underlies computability theory. Girard built his system directly on the lambda calculus of Church and Curry.
Carried by Alonzo Church; Haskell Curry.
Lambda Calculus led to Typed Lambda Calculus in Type Theory
Church added a simple type discipline to his untyped lambda calculus to avoid the Kleene-Rosser inconsistency, so the typed calculus grew directly out of the untyped one.
Carried by Alonzo Church; A Formulation of the Simple Theory of Types (1940).
Lambda Calculus influenced Functional programming in Programming Paradigms
The computability-theoretic lambda calculus provided the reduction and substitution model that functional languages implement; McCarthy's Lisp drew directly on it as a notation for functions.
Carried by Alonzo Church; John McCarthy.
Lambda Calculus led to Simply Typed Lambda Calculus in Type Systems
Church's simply typed lambda calculus was obtained by adding a simple type discipline to his earlier untyped lambda calculus, restricting the terms that could be formed.
Carried by Alonzo Church; A Formulation of the Simple Theory of Types (1940).
Lambda Calculus influenced Computability Theory in Mathematical Logic
Church's lambda calculus, introduced in the early 1930s, provided one of the formalizations of computability that computability theory unified with Turing machines. Church used lambda-definability to establish undecidability results.
Carried by Alonzo Church.
Lambda Calculus influenced Functional programming in Programming Languages
The lambda calculus as a computability formalism, developed by Church, provided the theoretical basis for functional programming's treatment of functions as first-class computable values. Lisp's design drew on this formalism.
Carried by Alonzo Church; John McCarthy.
General recursive function rival of Lambda calculus in Pl Semantics
Church's lambda-definability and Gödel–Herbrand's general recursiveness were proposed independently in 1934–36 as competing analyses of effective calculability. Church and Kleene proved them equivalent, and the equivalence became a cornerstone of the Church–Turing thesis.
Carried by Alonzo Church; Stephen Kleene; Kurt Gödel.
General recursive function grew out of Gödelian metamathematics in Logic
Gödel introduced the general recursive functions in 1934 while arithmetising metamathematics for his incompleteness theorems. The recursion-theoretic notion of computability grew directly out of that metamathematical programme.
Carried by Kurt Gödel; Stephen Kleene.
General recursive function influenced Computability Theory in Mathematical Logic
Gödel's general recursive functions, defined in 1934, were one of the formalizations of effective calculability that computability theory unified. Turing and Church showed these coincided with their own notions.
Carried by Kurt Gödel; Alan Turing; Alonzo Church.
General recursive function influenced Church–Turing thesis in Recursion Theory
Gödel's general recursive functions, developed from Herbrand's suggestions in 1934, supplied one of the formal explications that Church and Turing's thesis identified with effective calculability.
Carried by Kurt Gödel; Jacques Herbrand.
Church–Turing thesis influenced by Turing machine computability in Automata
Turing's analysis of machine computability was one of the two pillars of the thesis, and the thesis in turn codified his notion as the definition of effective calculability. The two are historically inseparable.
Carried by Alan Turing.
Turing machine influenced Von Neumann architecture in Digital Systems
Von Neumann's EDVAC report explicitly modelled the stored-program computer on Turing's universal machine, adopting the idea of a finite control reading instructions and data from one tape-like memory.
Carried by John von Neumann; Alan Turing; First Draft of a Report on the EDVAC (1945).

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 ComputabilityRelated fields
Fields its ideas are linked to
- Recursion Theory 22 links
- Mathematical Logic 10 links
- Logic 8 links
- Algorithms 6 links
- Automata 6 links
- Theory Of Computation 6 links
- Descriptive Set Theory 3 links
- Type Theory 2 links
- Foundations Of Mathematics 2 links
- Philosophy Of Artificial Intelligence 2 links
- Complexity Theory 2 links
- Quantum Computation 2 links