The theory of computation is the formal study of what can be computed and how efficiently those computations can be carried out. It lies at the intersection of mathematics and logic, and is usually considered a foundational area of computer science. Researchers in this field ask two broad questions: which problems are solvable by an abstract computing device, and for those that are solvable, what resources (time, memory, randomness) are required?
Core branches and concepts
The subject is commonly divided into several interrelated subfields. Computability theory (also called recursion theory) investigates whether a problem can be solved at all by any algorithmic procedure, typically modeled by idealized machines such as the Turing machine. Complexity theory refines this by classifying solvable problems according to the resources needed by their best algorithms. A third area, automata and formal language theory, examines restricted models of computation (finite automata, pushdown automata) and the sets of strings they recognize.
Important distinctions
- Decidable vs undecidable: Some decision problems can always be answered correctly by an algorithm (decidable), while others, like the halting problem, are provably undecidable.
- Tractable vs intractable: Within decidable problems, complexity theory separates those solvable with feasible resources (often called “tractable”) from those that appear to require impractical time or space.
- Worst-case and average-case: Complexity can be measured by the worst-case cost of solving instances or by more nuanced average-case analyses.
Historical background
The modern theory of computation emerged in the 1930s and 1940s from efforts to formalize the notion of algorithm and to answer decision problems posed in mathematical logic. Influential concepts were introduced by logicians who defined mechanical procedures for symbol manipulation; the Church–Turing perspective led to the Turing machine as a central abstract model. Later generations formalized complexity classes and reductions between problems, giving a language to compare algorithmic difficulty.
Applications and examples
Beyond its theoretical interest, the theory of computation underpins many practical areas. Complexity results guide algorithm design and show when improved algorithms are unlikely. Computability and decidability inform program verification, compiler construction, and formal methods used to prove software and hardware correctness. Cryptography depends on presumed hardness of certain problems, an idea rooted in complexity theory. Typical illustrative problems include the halting problem (undecidable), various language recognition problems in automata theory, and optimization or satisfiability problems whose classification (e.g., NP-complete) shapes practical expectations.
Why it matters
Understanding which problems are solvable and which are efficiently solvable sets fundamental limits on computation. This knowledge helps computer scientists decide where to focus engineering effort, when to seek approximations or heuristics, and how to build reliable systems. For further reading on foundational topics and formal definitions, see resources in computational models and introductory texts linked from surveys such as mathematics portals and discipline guides at computer science departments. Additional materials and community-maintained references are available via academic compendia and tutorial collections referenced on research pages about Turing machines and about complexity.
Key techniques in the field include reductions (showing that solving one problem would solve another), complexity class separations and completeness proofs, and the design of abstract machine models that capture intuitive computational power. Whether one approaches the subject for theoretical insight or practical guidance, the theory of computation provides a rigorous framework for asking what can be computed and at what cost.