Theory of computation

Lore & Background

Pioneers of the theory of computation include Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann, and Claude Shannon. The field studies abstract machines called automata, which are used as theoretical models for computing machines and for proofs about computability. Formal language theory is closely linked with automata theory, and languages are classified by the Chomsky hierarchy.

Reader's Guide

The theory of computation is significant because it establishes the fundamental limits of what can be computed, how efficiently it can be computed, and the models used to study computation. Its three branches—automata theory, computability theory, and computational complexity theory—provide the theoretical underpinnings for all of computer science. Key results include the unsolvability of the halting problem and Rice's theorem in computability theory, and the P versus NP problem, a major open question in complexity theory. The Turing machine is a central model of computation, representing what many consider the most powerful possible 'reasonable' model, per the Church–Turing thesis. The field's legacy includes the development of other equivalent models such as lambda calculus, combinatory logic, μ-recursive functions, Markov algorithms, and register machines, which together form the foundation for understanding computation.

Did You Know?

• The halting problem cannot be solved by a Turing machine and is one of the most important results in computability theory.
• Rice's theorem states that for all non-trivial properties of partial functions, it is undecidable whether a Turing machine computes a partial function with that property.

Classifying the Inherent Difficulty of Computation

Computational complexity theory sits at the intersection of theoretical computer science and mathematics, with a central mission: to sort computational problems into categories based on how much resource they demand and to map the connections between those categories. At its heart, the field takes the everyday intuition that some tasks are simply harder than others and gives it a rigorous mathematical foundation. It does so by building formal models of computation and then measuring, in precise quantitative terms, how much time, memory, or other resources a problem consumes. Crucially, the theory asks about inherent difficulty—meaning the resources required regardless of which algorithm one might devise. Beyond time and storage, the field also tracks other resource dimensions such as communication volume, circuit gate counts, and processor counts in parallel settings. One of its most visible contributions is establishing the practical boundaries of what machines can accomplish. The famous P versus NP question, listed among the seven Millennium Prize Problems, lives squarely within this domain.

Problems, Instances, and the Art of Abstraction

A foundational conceptual move in complexity theory is the sharp separation between a problem and any single instance of that problem. A computational problem is treated as an infinite family of concrete inputs, each paired with a set of valid outputs. The input string for a given case is called an instance, and it should never be conflated with the overarching question itself. Consider primality testing: the problem is the abstract question of whether a number is prime, while an instance is a specific number like 15, yielding the answer no. Because individual answers are so context-bound, complexity theory deliberately studies the problem as a whole rather than any single instance, seeking classifications that hold across the entire infinite collection.

Decision Problems as Formal Languages

Among the many objects complexity theory examines, decision problems occupy a particularly central role. A decision problem is one whose answer is binary—yes or no, equivalently 1 or 0. This binary structure lets theorists recast each decision problem as a formal language: the set of all input strings that produce a yes answer forms the language's members, while those yielding no fall outside it. The algorithmic task then becomes deciding whether a given string belongs to that language. If the algorithm returns yes, it accepts the string; if no, it rejects. A concrete illustration is graph connectivity: the input is an arbitrary graph, and the question is whether it is connected. The associated formal language is the collection of all connected graphs, though pinning down a precise definition requires first choosing how to encode graphs as binary strings. This language-theoretic framing provides a clean, uniform vocabulary for comparing problems, designing algorithms, and proving lower bounds on the resources any correct solution must expend.

Delineating the Boundaries with Neighboring Fields

Computational complexity theory shares territory with two closely related disciplines—analysis of algorithms and computability theory—yet draws its boundaries in distinct ways. Analysis of algorithms focuses on a specific, named algorithm and measures the resources that particular procedure consumes on a given problem. Complexity theory, by contrast, zooms out to ask a far broader question: what is the minimum resource cost across every conceivable algorithm that could tackle the same problem? It classifies problems as solvable or unsolvable under appropriately restricted resource budgets. Computability theory, meanwhile, takes a different stance: it asks which problems are solvable in principle by some algorithm, without imposing any resource ceiling. Imposing such restrictions on available resources is precisely what separates complexity theory from computability. Additionally, while some theorems assume a particular input encoding—binary strings for integers, adjacency matrices or lists for graphs—the field strives to keep its results independent of any single encoding choice, relying on the fact that different representations can be converted into one another efficiently.