Theory of Computation: What Can and Cannot Be Computed

Your code editor will warn you about an unused variable. It will not reliably warn you that your program never stops. For some loops it can tell; for others it cannot, and the surprise is that this is not a failing of today's editors. In 1936 it was proved that no program, however clever and however much time it is given, can look at every program and say whether it will finish.

That is the opening of the theory of computation: a mathematical map of what machines can do at all, what they can do only slowly, and what they can never do. A graduate keeps the map for life. It tells them when to stop trying to build a perfect bug finder, and when a problem is "hard" in the specific, technical sense that decades of the best minds have not cracked it.

What "computable" means

The theory starts by shrinking every question to a yes/no one: is this number prime? Does this string match? Does this program halt? A question is decidable if some program answers it correctly, always, in finite time, for every input. Not fast; just finishing and right. (If speed matters, that is the later half of the course.)

But "some program" in which language? Here comes the quiet miracle. In 1936 Alonzo Church (with the lambda calculus) and Alan Turing (with his machines) gave two completely different definitions of "effectively calculable", and they turned out to describe exactly the same set of functions. Many later formalisms agree. The Church-Turing thesis says this set is what any step-by-step method can compute. It cannot be formally proved, because "any method" is an informal idea, but it has stood for ninety years, and some theorists simply treat it as the definition of computable.

Finite automata and regular expressions: machines with no memory

Start with the weakest useful computer: a finite automaton. It has a fixed handful of states (think of lights on a panel), reads its input one symbol at a time, and on each symbol moves to a state determined only by where it is and what it read. No tape, no counter, no scratch paper. At the end it says accept or reject.

That is already more useful than it sounds. A turnstile, a vending machine's coin logic and the text matcher in your search box are automata. Stephen Kleene showed in 1951 that the languages such machines accept are exactly the ones you can describe with regular expressions: patterns built from letters, "or", "followed by" and "repeat". Ken Thompson built them into text editors in the late 1960s (first QED, then Unix's ed), which is where grep comes from.

The "divisible by 3" machine shows the trick of automata: it does not remember the number, only the remainder, three possible values. The limit is just as clear. A machine with k states can never tell apart more than k different histories. Ask it to check that a string has as many as as bs, aⁿbⁿ, and it would have to remember n, an unbounded number. No fixed number of states suffices.

A practical footnote: the regex engines in programming languages are stronger than the theory's regular expressions (they add "backreferences"), and that extra power has a price. Some patterns can make a backtracking engine take exponential time, a real attack vector known as ReDoS.

Grammars: nesting needs a stack

To handle aⁿbⁿ or matching brackets, add one thing: a counter or, more generally, a stack. A machine with a stack (a pushdown automaton) recognises exactly what a context-free grammar generates. A grammar is a list of rewriting rules. For balanced brackets: S → ( S ) S or S → ε (the empty string). Start from S and keep rewriting.

Noam Chomsky described this ladder in 1956, and it has four rungs: regular (finite automata), context-free (stack), context-sensitive (a bounded tape) and unrestricted (a full Turing machine). Each contains the one below. aⁿbⁿ is context-free but not regular; aⁿbⁿcⁿ is beyond context-free. Programming languages are specified by context-free grammars, which is why the compiler course (34/30) begins with them: parsing your code is turning a flat string back into the tree the grammar generated.

Turing machines: adding a tape

Give the machine an endless tape it can read, write and move along, and it stops being limited. That is a Turing machine, and the thesis above says it is as powerful as any computer can be. Nothing else is added: states, a tape, a head, a table of rules.

Here is the proof that the tape matters. The machine below decides aⁿbⁿ, the language that defeats every finite automaton. Its method is what a person would do with a pencil: cross off the first a (mark it X), run right to the first unpaired b (mark it Y), return left to the X, and repeat. If every a and b are crossed off together, accept.

A Turing machine can also read another machine's rule table off its own tape and imitate it. Turing called this the universal machine; it is the idea of a stored program, and every phone is one. The same fact sets up the next result.

The halting problem: a proof you can say out loud

Claim: no program H exists that, given any program P and input, always correctly answers "halts" or "loops forever". Here is the proof in words, in the style of Cantor's diagonal argument.

Suppose H existed. Build a mischievous program D that takes a program as its input and asks H what that program does when fed its own text. If H says "halts", D loops forever. If H says "loops", D halts at once. Now run D on D. If it halts, then H said it loops, so H was wrong. If it loops, H said it halts, wrong again. Either way H is wrong about D, so no correct H exists.

Turing proved this in a paper that went to press in 1936 and appeared in 1937; he did not use the word "halting", which came from Martin Davis later. Church reached a closely related result for his own system a little earlier in 1936. The deeper consequence is Rice's theorem: every non-trivial question about what a program does (will it ever crash, will it ever print this word, does it compute the same thing as that other program?) is undecidable in general.

What this does not say matters. Particular programs can be analysed, and good tools prove many programs terminate. And a computer with strictly finite memory does eventually repeat a state, so for it halting is decidable in principle, though the number of states is so astronomical that the fact is of no practical use. The result says: no one method handles all programs.

P, NP and NP-completeness: easy to check, hard to find

Now suppose the answer is computable, and the question is cost. P is the class of yes/no problems solvable in polynomial time (like n, n log n, n²): sorting, shortest paths, is this number prime. NP is the class where a proposed "yes" answer can be checked in polynomial time: the "N" is for "nondeterministic", an old way of saying "if you were handed a certificate". Every problem in P is in NP. The open question, P = NP?, asks whether checking is really easier than finding.

That formula is an instance of SAT, satisfiability: is there a setting of the variables that makes the whole formula true? Stephen Cook showed in 1971 (and Leonid Levin independently, in work published in 1973) that SAT is NP-complete: every problem in NP can be translated into it in polynomial time. That translation is called a reduction, and it is the theory's most useful move. If problem A reduces to problem B, then a fast method for B would give a fast method for A.

A small reduction you can feel: in a friendship graph, a group of people who all know each other (a clique) is exactly a group of strangers in the opposite graph (an independent set). Solve one problem and you have solved the other. In 1972 Richard Karp used reductions to show that 21 well-known problems, including clique, vertex cover, the Hamiltonian circuit and knapsack, are all NP-complete. Many hundreds more have followed.

Opinion is lopsided but it is opinion. In a poll of researchers by William Gasarch in 2018, about 88% believed P is not equal to NP. Practically, NP-complete does not mean hopeless: industrial SAT solvers handle enormous real instances, and heuristics give good answers. It means no known method is fast on every instance, so engineers stop hunting for a perfect one and settle for good enough.

What quantum computers do and do not change

It is tempting to say a quantum computer tries every answer at once. That is wrong, and it matters. A quantum computer works on qubits, whose states combine as amplitudes that can cancel or reinforce. A clever algorithm arranges the cancellation so that wrong answers fade and the right one is likely when you finally measure. A measurement returns a single result, so there is no free "all at once".

So the honest summary: quantum computers do not change what is computable, only how fast certain problems can be solved, and the problems with large known gains (factoring, simulating quantum physics) are specific, not "everything". The classical definition of efficient computing, the "extended" Church-Turing thesis, is the part under threat, not the original. On the hardware, Craig Gidney estimated in 2025 that factoring a 2048-bit RSA number would need fewer than a million noisy qubits running for under a week, noting that today's devices have at most a few thousand noisy qubits and none is fully error-corrected. That is an estimate, and the engineering is hard.

What a graduate just sees

• Every computer, big or small, can compute the same set of things; only speed differs.
• A machine with finite memory cannot count without bound; nesting needs a stack.
• Languages form a ladder: regular, context-free, context-sensitive, unrestricted.
• Self-reference can be turned into a proof: the halting problem is undecidable.
• Any non-trivial question about what a program does is undecidable in general (Rice).
• Easy to check does not mean easy to find; that gap is P versus NP.
• A reduction transfers difficulty: "if I could solve B, I could solve A".
• Quantum computers are fast at some structured problems, not at everything, and they compute nothing new.

Where it shows up next

• Compilers (34/30): regular expressions tokenise your code and context-free grammars parse it.
• Algorithms (34/24) looks back: the salesman's tour and 2ⁿ blow-ups are exactly NP-hard territory.
• Security (34/33): modern cryptography leans on problems believed to be hard, which is why Shor's algorithm is such news.
• Software engineering (34/31): static analysers and type checkers are deliberately approximate, because Rice's theorem forbids exactness.
• In life: the search box, the spell-checker, logistics planners and chip designers all use SAT solvers or heuristics for NP-complete problems.

If you want to go deeper

• 📘 Textbook: Michael Sipser, Introduction to the Theory of Computation (Cengage, 3rd ed.): the standard text, famous for its clarity.
• 📘 Textbook: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (4th ed.), the NP-completeness chapter.
• 📘 Gentler: Scott Aaronson, Quantum Computing since Democritus (Cambridge University Press, 2013): an entertaining tour from Turing to quantum.
• 🌐 Free course: MIT OpenCourseWare 6.045J / 18.400J, Automata, Computability, and Complexity (Spring 2011, taught by Scott Aaronson), with lecture notes and problem sets.