No computer program can decide, in general, whether another program will halt
It sounds like a simple question: given a program and its input, will it eventually finish or run forever? Yet no Turing machine can answer it for every case. This halting problem is one of the central results of computability theory, a concrete task that is easy to state and provably impossible to solve.
The theory of computation asks what problems algorithms can solve, how efficiently, and how exactly. It has three main branches: automata and formal languages, computability, and complexity. All three circle one question, what the fundamental powers and limits of computers are.
To reason rigorously, researchers use abstract models of computing, above all the Turing machine. It is simple to describe, easy to prove things about, and widely regarded, under the Church–Turing thesis, as the most powerful reasonable model possible. Its unlimited memory looks unrealistic, but any problem it actually decides needs only a finite amount, so an ordinary computer could in principle do the same.
Much of computability theory builds on the halting result. Rice's theorem extends it dramatically: for any non-trivial property of the functions programs compute, there is no general way to decide whether a given program has that property. Automata theory, meanwhile, studies idealised machines, named from a Greek word for something acting by itself, and classifies them by the formal languages they can recognise. Those languages climb the Chomsky hierarchy, each level more expressive than the one below and matched by a more capable type of machine. Complexity theory then asks not just whether a problem can be solved but at what cost, counting steps taken and memory used.
The field's lineage stretches surprisingly far back; its pioneers are said to include Ramon Llull as well as Alonzo Church, Kurt Gödel, Alan Turing, Rózsa Péter and Claude Shannon. In the last century it split from mathematics into a discipline with its own conferences, FOCS from 1960 and STOC from 1969, and its own honours, including the Gödel Prize, founded in 1993, and the Knuth Prize, founded in 1996.
Source: Theory of computation
