1.7 — Theory of Computation

We have built a machine from the ground up — switches, gates, memory, a CPU, the storage that feeds it. Now we ask a different kind of question, and it's one of the deepest humans have ever asked: not how do we compute, but what can be computed at all? Is there anything a computer can never do, no matter how fast, how much memory, how clever the programmer? The astonishing answer — proven in the 1930s, before the first electronic computer existed — is yes. There are precisely-defined problems no computer can ever solve, and this chapter shows you one, and why the limit is permanent. Along the way we build the ladder of theoretical machines that underpins regular expressions, programming-language parsers, and the most famous open problem in all of science: P vs NP.

This is the most abstract chapter in Part 1, and the most beautiful. No hardware here — pure ideas about the limits of the possible.

1. A ladder of machines — models of computation

To reason about "what can be computed," we study idealized machines, each strictly more powerful than the last. Notice they are the finite state machines of 1.2, given more and more memory.

Finite automata — memory of a fixed size. The weakest model is the finite automaton: exactly the FSM from 1.2 — a fixed set of states, transitions on input, no extra memory. It can recognize patterns that need only bounded memory: "does this string contain cat?", "is this a valid binary number ending in 0?". The class of patterns it can handle is called the regular languages, and here's the payoff — this is the theory behind regular expressions (regex). Every /^\d{3}-\d{4}$/ you write compiles to a finite automaton. And knowing the theory tells you its limits: a finite automaton cannot count arbitrarily, because counting needs unbounded memory. It cannot check whether parentheses are balanced — ((())) vs (() — because that requires remembering how many are open, without limit. (This is the real, theoretical reason you famously "can't parse HTML with regex": nested tags need counting, and regex can't count.)

Pushdown automata — add a stack. Give the machine a stack (a memory where you can only push and pop the top — Chapter 4.7) and it becomes a pushdown automaton, able to recognize context-free languages. Now it can match nested parentheses: push on (, pop on ), check the stack empties. This is exactly why parsers for programming languages (Part 3) use a stack — nested structure (brackets, blocks, expressions) is context-free, and the stack remembers the nesting. The ladder is already paying rent: it tells you which tool fits which shape of problem.

Turing machines — add unlimited memory. At the top, give the machine an infinite tape it can read, write, and move along freely. This is the Turing machine, defined by Alan Turing in 1936 — and it is the definition of computation itself.

2. The Turing machine and the Church–Turing thesis

A Turing machine is almost insultingly simple: an infinite tape of cells, a head that reads and writes one cell and moves left or right, and a finite table of rules ("in state S reading symbol X, write Y, move left, go to state T"). That's all. Yet Turing proved this trivial device can compute anything that any other computer can compute — anything computable at all.

This is captured in the Church–Turing thesis: any function that can be computed by any effective procedure can be computed by a Turing machine. Your laptop, a supercomputer, a quantum computer (with caveats about speed, not ability), a human following rules with pencil and paper — all compute exactly the same set of things a Turing machine can. They differ wildly in speed, but not in the boundary of the possible. When we say a programming language is Turing-complete (as almost all are — even, accidentally, some that weren't meant to be), we mean it can express any computation a Turing machine can. This is why the choice of language never changes what's computable, only how pleasantly. The Turing machine is the yardstick against which "computable" is defined.

Figure 1 — A Turing machine. An infinite tape, a head that reads/writes/moves, and a finite rule table. Trivial to describe, yet the exact boundary of what any machine can compute.

3. The halting problem — a wall no machine can cross

Now the shock. Turing used his machine to prove that some problems are undecidable — no algorithm can solve them, ever. The famous one is the halting problem: given a program and its input, decide whether that program will eventually halt (finish) or loop forever.

It sounds solvable — just run it and see? But "run it and see" never terminates for a program that loops forever; you'd wait eternally, never sure if it's about to stop. Turing proved that no general algorithm can decide this for all programs — and the proof is a piece of logical judo worth seeing, because its shape recurs across mathematics.

Suppose, for contradiction, a perfect halt-detector halts(program, input) exists, always correctly returning yes it halts or no it loops. Then build a mischievous program Trouble:

Trouble(program):
    if halts(program, program) is "halts":
        loop forever
    else:
        halt

Trouble asks the oracle what a program does when fed itself, then does the opposite. Now the fatal question: what does Trouble(Trouble) do?

• If halts says Trouble(Trouble) halts, then by its code Trouble loops forever — contradicting the oracle.
• If halts says it loops, then by its code Trouble halts — contradicting the oracle again.

Either way the oracle is wrong. So the perfect halt-detector cannot exist. This isn't "we haven't found the algorithm yet" — it's a proof that no such algorithm can possibly exist, as certain as \sqrt{2} being irrational. (The self-reference trick — a thing asking about itself and doing the opposite — is the same engine behind Gödel's incompleteness theorems and Cantor's proof that some infinities are bigger than others. It is one of the great ideas of 20th-century thought.)

This is not idle philosophy. It means no tool can perfectly detect all infinite loops, decide whether two programs are equivalent, determine if code is malware in general, or verify arbitrary program correctness automatically. Rice's theorem generalizes it: essentially any non-trivial question about what a program does (as opposed to how it's written) is undecidable. Whole industries — static analyzers, type checkers, verifiers — live in the shadow of this wall, using approximations and heuristics precisely because the perfect answer is provably impossible. When your linter says "this might be an infinite loop" instead of "this is," it's not being lazy; it's respecting Turing.

4. When it can be solved — but not quickly: P vs NP

Undecidable problems can't be solved at all. But among the problems that can be solved, there's a second, more practical hierarchy — about how long solving takes as the input grows. This is complexity theory, and it holds the most famous open question in computer science.

Two classes matter most. P ("polynomial time") is the class of problems solvable reasonably fast — where the time grows as a polynomial in the input size (n, n^2, n^3…). These are the "tractable" problems: sorting, searching, shortest paths. NP ("nondeterministic polynomial time") is the class of problems whose solutions can be checked quickly, even if finding one seems to require brute force. The classic example is the Boolean satisfiability problem (does a logic formula have an assignment making it true?), and its cousins: the traveling salesman, optimal scheduling, packing a knapsack. Given a candidate answer you can verify it in a blink — but finding it among exponentially many possibilities seems to need trying (nearly) all of them.

The question — does P = NP? — asks: if a solution can be checked quickly, can it also be found quickly? Is verifying genuinely easier than solving, or are we just not clever enough to find the fast algorithms? It is unresolved, carries a $1,000,000 Clay Institute prize, and nearly every expert bets P ≠ NP (finding is genuinely harder than checking) — but no one can prove it. The stakes are civilizational: a huge swath of hard problems are NP-complete, meaning they're the hardest in NP and all equivalent — a fast algorithm for one would instantly solve them all, collapsing NP into P. That would revolutionize logistics, biology, and AI overnight — and simultaneously break nearly all modern cryptography, since encryption (Part 8) relies on certain problems being easy to check (verify a password) but infeasible to solve (crack it). The security of the internet is, in a real sense, a bet that P ≠ NP.

For you as an engineer, the practical takeaway arrives long before the prize is claimed: when you recognize a problem as NP-complete (and Part 4 teaches the recognition), you stop looking for a perfect fast algorithm — none is known and probably none exists — and pivot to approximations, heuristics, or exploiting special structure. Knowing a wall is there saves you from running at it. That reflex — "this smells NP-complete, don't seek the exact optimum" — is one of the most practical gifts of theory.

5. The expert lens

The limits are permanent, not technological. Undecidability and (almost certainly) the hardness of NP-complete problems are not about slow hardware or missing cleverness — they're mathematical bedrock. No quantum computer, no future breakthrough, no amount of Moore's law repeals the halting problem. This is oddly liberating: it tells you which walls are real, so you stop trying to tunnel through them and start designing around them.

Theory quietly shapes daily tools. The ladder isn't academic decoration. Regular (finite automata) → your regex engine and lexers. Context-free (pushdown automata) → your language's parser and why regex can't parse nested structure. Turing-complete → why a config language that gains loops and conditionals suddenly has all the risks of a full program (and why some are deliberately kept not Turing-complete for safety). NP-completeness → why your scheduler, route-optimizer, or dependency-resolver uses heuristics. Recognizing which rung a problem sits on tells you which tool — and which impossibility — you're dealing with.

Verifying vs finding is a lens on the whole world. The P-vs-NP intuition — that checking an answer can be far easier than producing one — echoes everywhere: it's why we can grade a proof faster than discover it, why cryptography works, why a Sudoku is fun (hard to solve, trivial to check). Carrying that distinction sharpens how you think about problems far beyond computers.

Next chapter: we've reached the limits of what can be computed. 1.8 closes Part 1 with the limits of information itself — Claude Shannon's theory of how much data a message really contains, the hard floor on compression, and how we send bits reliably through a noisy world. The forbidden-zone story of 1.1 gets its mathematics at last.

Recall

• Models of computation form a ladder of increasing power: finite automata (regular languages, = regex; can't count) → pushdown automata (context-free, +a stack; can match nesting, = parsers) → Turing machines (unlimited tape; the definition of computable).
• The Church–Turing thesis: every effective computer computes the same set of things a Turing machine can — differing in speed, not in the boundary of the possible. Turing-complete languages can all express the same computations.
• The halting problem is undecidable: no algorithm can decide, for all programs, whether they halt — proven by a self-reference contradiction. So perfect loop-detection, malware-detection, and program-equivalence are impossible in general (Rice's theorem generalizes this).
• P = solvable in polynomial time; NP = solutions checkable in polynomial time. P vs NP (does checkable ⇒ findable?) is unsolved, worth $1M; NP-complete problems are the hardest in NP and all equivalent. Most crypto bets P ≠ NP.
• Practical reflex: recognizing undecidability or NP-completeness tells you to stop seeking a perfect/fast solution and design around the wall (heuristics, approximations).

Self-test: Why can't a regular expression check balanced parentheses? What does the Church–Turing thesis claim? Sketch why the halting problem is undecidable. What's the difference between P and NP, and why would P = NP break cryptography?

Quiz Bank

FoundationalWhat are regular languages, and what's their real-world face?

Regular languages are the patterns recognizable by a finite automaton (an FSM with no extra memory). Their real-world face is regular expressions: every regex compiles to such an automaton. The theory also bounds them — with only finite states they can't count without limit, so they can't match balanced/nested structures (e.g. parentheses or HTML tags). That's the formal reason "don't parse HTML with regex."

FoundationalWhy do programming-language parsers use a stack?

Because language syntax (nested brackets, blocks, expressions) is context-free, and context-free languages are exactly what a pushdown automaton — a finite automaton plus a stack — can recognize. The stack remembers nesting depth (push on open, pop on close), which a finite automaton alone can't do. This is why Part 3's parsers are stack-based.

AppliedState the Church–Turing thesis and one practical consequence.

The Church–Turing thesis holds that any function computable by any effective procedure is computable by a Turing machine — so all general-purpose computers (and a human with pencil and paper) can compute the same set of things, differing only in speed. Practical consequence: since almost every programming language is Turing-complete, the choice of language never changes what is computable, only how conveniently — so "can this be done at all?" is language-independent.

InterviewExplain the halting problem and why it's undecidable.

The halting problem asks for a general algorithm that decides, for any program+input, whether it halts or runs forever. It's undecidable: assume a perfect halts() exists, then build Trouble(p) that halts if halts(p,p) says "loops" and loops if it says "halts." Asking what Trouble(Trouble) does yields a contradiction either way, so halts() cannot exist. It's a proof of impossibility, not a gap in knowledge — hence perfect loop/malware/equivalence detection is impossible in general (Rice's theorem extends this to any non-trivial semantic property).

InterviewWhat are P and NP, and what is the P vs NP question?

P is the class of decision problems solvable in polynomial time (tractable — sorting, shortest path). NP is the class whose candidate solutions can be verified in polynomial time (e.g. Boolean satisfiability, traveling salesman as a decision problem). P vs NP asks whether every quickly-checkable problem is also quickly-solvable (P = NP) or not. It's open, worth $1M; the consensus bet is P ≠ NP. Problems that are NP-complete are the hardest in NP and mutually reducible — solve one in P and you solve them all.

StaffWhy does most of modern cryptography implicitly assume P ≠ NP, and what would P = NP mean for it?

Cryptography relies on problems that are easy to verify but hard to solve — e.g. checking a password/signature is fast, but inverting a hash or factoring a large number (breaking RSA) is believed infeasible. That asymmetry is precisely the P-vs-NP intuition: verification in P, solving apparently not. If P = NP (constructively, with practical constants), then finding solutions would be as easy as checking them — an efficient algorithm would exist to crack these problems, and essentially all widely-used public-key crypto would break, collapsing internet security. So the practical security of modern systems is, in effect, a standing bet that P ≠ NP (and that these specific problems are genuinely hard). Note the caveat: a non-constructive or galactic-constant proof of P = NP might not immediately break anything — but the risk is existential enough that the assumption is foundational.

Flashcards

FlashThree rungs of the computation ladder

Finite automata (regular / regex) → pushdown automata (context-free / parsers, +stack) → Turing machines (computable, +infinite tape).

FlashWhy regex can't match balanced parentheses

Finite automata have no unbounded memory, so they can't count nesting depth; balanced parens require counting.

FlashChurch–Turing thesis

Anything computable by any effective procedure is computable by a Turing machine — all general computers compute the same set, differing only in speed.

FlashHalting problem

No algorithm can decide, for all programs, whether they halt — undecidable, proven by self-reference contradiction.

FlashP vs NP in one line

P = solvable fast; NP = checkable fast; open question: are they the same? (Likely not; $1M prize.)

FlashNP-complete significance

The hardest problems in NP, all mutually reducible — one fast solution would solve them all (and imply P = NP).

Scenario Drill

DrillA product manager asks you to build a feature that 'scans any uploaded user script and guarantees it never contains an infinite loop before we run it.' How do you respond, grounded in theory?

Explain that a perfect, general guarantee is provably impossible, not merely hard: detecting whether an arbitrary program halts is the halting problem, which Turing proved undecidable — no analyzer can be correct for all inputs (Rice's theorem extends this to essentially any non-trivial behavioral property). So "guarantee for any script" cannot be delivered. Then pivot to what is achievable, which is what real systems do: (1) constrain the language so it's not Turing-complete — remove unbounded loops/recursion (a deliberately limited config or expression language can be guaranteed to terminate); (2) impose runtime limits — execute in a sandbox with a CPU/time budget and kill anything that exceeds it (sidestepping the undecidable question by not answering it); (3) conservative static checks that catch common patterns and reject or warn on the rest, accepting false positives. The professional move is reframing an impossible spec into a decidable, bounded one — and citing why the original was impossible so the constraint isn't seen as a cop-out.