The theory of computation is the branch of mathematics and computer science that asks what problems can be solved by computation, and how efficiently. It provides the deep foundations on which all of computing rests.
At its heart lies a deceptively simple question: what does it mean to compute something? The theory seeks a precise definition of a "procedure" or "algorithm," a finite set of clear steps that can be carried out mechanically, without insight or intuition, to arrive at an answer. Pinning this down turned out to be surprisingly deep.
The theory's most profound discovery is that some problems can be solved by an algorithm while others provably cannot, no matter how powerful the computer or how long it runs. There are clear, well posed questions for which no procedure can ever exist. Computation, it turns out, has hard limits built into the fabric of mathematics.
In 1936, the British mathematician Alan Turing imagined a simple abstract device, now called the Turing machine, that reads and writes symbols on an endless tape according to fixed rules. Despite its extreme simplicity, it can carry out any computation that any computer can. It gave the word "computable" a precise, universal meaning.
Turing used his machine to prove a stunning result: there can be no general algorithm that decides, for every program, whether it will eventually stop or run forever. This "halting problem" is provably undecidable. It was among the first concrete examples of a question that no computation can ever answer.
Remarkably, several mathematicians arrived at different definitions of computation at around the same time, and all proved equivalent. This led to the Church-Turing thesis, the widely held belief that anything that can be computed by any conceivable method can be computed by a Turing machine. It anchors the whole field.
Beyond what can be computed at all lies the study of how much time and memory a computation needs. Some problems can be solved quickly, while others, though solvable in principle, would take longer than the age of the universe for large inputs. Sorting problems by their difficulty is the work of complexity theory.
The field's most famous open problem is whether the class of problems whose answers can be quickly checked is the same as the class that can be quickly solved, known as P versus NP. Most experts believe they differ, but no one has proved it. It is one of the great unsolved problems in all of mathematics.
The theory of computation underlies the design of programming languages, compilers, and cryptography, and it tells engineers which problems are worth attacking and which are hopeless. By drawing the boundaries of what machines can and cannot do, it provides the intellectual foundation of the entire digital age.
