Computability theory

Computability theory emerged in the 1930s from the work of Alan Turing, Alonzo Church, and Kurt Gödel, who each proposed formal models of computation: Turing machines, lambda calculus, and general recursive functions, respectively.¹ These models were shown to be equivalent in power, leading to the Church-Turing thesis, which states that any effectively computable function can be computed by a Turing machine.² The field quickly established the existence of problems that no algorithm can solve, most famously the halting problem, which Turing proved undecidable in 1936.³ This foundational work not only defined the limits of computation but also laid the groundwork for the development of digital computers and the theory of formal languages.

Central to computability theory is the concept of decidability: a problem is decidable if there exists an algorithm that always halts with a correct yes/no answer. The Church-Turing thesis formalizes the intuitive notion of “algorithm” by equating it with Turing machine computability.⁴ Problems that are not decidable are called undecidable; the halting problem is a canonical example. The field also classifies problems by their degree of unsolvability—the Turing degree—which measures the relative difficulty of undecidable problems using oracles.¹ Recursive functions, both primitive and general, provide a mathematical characterization of computable functions, and the arithmetical hierarchy organizes sets of natural numbers by the complexity of their definitions.

Beyond the halting problem, computability theory yields many undecidable problems, such as Rice's theorem, which states that any non-trivial property of the language of a Turing machine is undecidable.⁵ Gödel's incompleteness theorems are intimately connected, showing that any sufficiently powerful formal system cannot prove all true statements about arithmetic. Computability theory also underpins the theory of computation, influencing topics like automata theory, complexity theory, and algorithmic information theory. In modern computer science, it provides the theoretical basis for understanding the limits of software verification, automated theorem proving, and artificial intelligence.

Beyond the well-known undecidability results, computability theory reveals a rich structure of unsolvability. The Friedberg-Muchnik theorem (1956) demonstrated the existence of recursively enumerable sets that are Turing-incomparable, a milestone in the study of degrees of unsolvability.¹ The priority method, developed to prove this, became a central technique in recursion theory. Oracle machines extend Turing machines by allowing queries to external information, enabling the study of relative computability. The field also considers hypercomputation, hypothetical models that exceed Turing's limits, though these remain speculative. The application of computability theory to algorithmic learning theory and descriptive set theory continues to yield deep insights into the nature of computation and definability.

Turing machine

A mathematical model of computation that manipulates symbols on a tape according to a set of rules, used to define computability.

Decidable

A problem for which there exists an algorithm that always halts with a correct answer.

Undecidable

A problem for which no algorithm exists that always halts with a correct answer.

Church-Turing thesis

The claim that any function that can be effectively computed by an algorithm can be computed by a Turing machine.

Halting problem

The problem of determining, from a description of an arbitrary program and input, whether the program will finish running or continue forever.