Chapter Fourteen · The Limits of Computation
The Limits of Computation
The book ends by climbing from the smallest machine to the ceiling over all of them. Six topics go from state machines and the regex engine that can freeze a server, through the stack a parser needs and the Turing machine at the top of the ladder, to the questions no program can answer, the problems no known program answers quickly, and how engineers ship below both.
Every chapter so far has priced something: a lookup, a cache miss, a lock, a retransmission. Each price came from a layer underneath, and each could be lowered by a better structure, a better algorithm or a better machine. This chapter is about the prices that cannot be lowered, because they come from what computation itself is.
It starts small, with the finite state machine: a lexer, a turnstile, and the regular expression, where a backtracking engine turns one staff member's pattern into a Lantern search worker pinned at full CPU. It adds a stack and gets a parser, then an unbounded tape and gets the Turing machine, the model every real computer matches. At the top of that ladder it proves, in plain words, that some questions about programs have no answer at all, and it meets problems that have answers only exhaustive search is known to find.
The last topic is about working anyway. Approximations, heuristics, solvers and a narrower question are how package managers, schedulers and route planners ship every day, and cryptography turns hardness into protection. It closes the book on the question it opened with, what does this cost and why, and hands each chapter to the course that puts it to work.