Elements of the Theory of Computation

Climb one more rung and you reach the Turing machine, the device the whole book is quietly built toward. It looks barely more elaborate than what came before: an infinitely long tape divided into cells, a head that reads one symbol, writes one symbol, and shifts left or right, all governed by a finite table of rules. Yet Lewis and Papadimitriou make the case, carefully, that this humble object can carry out any computation that any machine could — that anything we would intuitively call an effective procedure, a Turing machine can perform.

This claim has a name, the Church-Turing thesis, and it is not a theorem but a proposal about what the word 'computable' should mean. The authors treat it with the seriousness it deserves. Every attempt to define computation more powerfully — adding tapes, adding randomness, dressing the machine up in the language of a modern programming environment — turns out to compute exactly the same set of functions. The tape-and-head model keeps winning. That convergence is the evidence that Turing captured something real rather than one arbitrary design among many.

The far side is the halting problem, and it is the emotional peak of the book. The question is almost insultingly simple to state: given a program and an input, will the program eventually stop, or will it loop forever? Every working programmer wishes they had a tool that answered this. Lewis and Papadimitriou prove, following Turing, that no such tool can exist. Not that it is hard to build, not that we lack the technology — that it is impossible in principle, for any machine whatsoever.

The proof is a piece of intellectual theater the authors present with real care. Suppose a halting-detector existed. Then we could build a second program that consults the detector about itself and then does the opposite of what the detector predicts — halting when it is told it will loop, looping when it is told it will halt. This contraption cannot consistently exist, so the detector it depended on cannot exist either. It is the same self-referential trap Georg Cantor used to show some infinities outrun others, turned into a statement about programs. A machine, reasoning about machines, corners itself.

Stepping back, the book's second half makes a subtler and, for daily life, more consequential point. Undecidability is a dramatic wall, but most of the problems we actually care about are decidable — a machine can solve them. The trouble is how long it takes. This is where complexity theory enters, and where Lewis and Papadimitriou shift from asking whether a problem can be solved at all to asking whether it can be solved before we run out of patience, or planet.

The dividing line they draw is between problems solvable in polynomial time — where the work grows manageably as the input gets larger — and problems that seem to demand exponential time, where adding a few items to the input can double the work, then double it again, until even a modest instance would outlast the universe. The first class, called P, is the practical world. The shadow over it is a family of problems, the NP-complete ones, that nobody has managed to place cleanly on either side. Scheduling, routing, packing, countless puzzles that look innocent turn out to belong to this family, all secretly the same problem wearing different clothes.

The book ends more or less where it began, with a machine simple enough to fit on a napkin, and the reader now able to see how much that napkin decides. From a tape, a head, and a finite table of rules, Lewis and Papadimitriou extract the halting problem, the hierarchy of what different machines can recognize, and the still-open frontier between the tractable and the merely possible. The friendliness of the writing never softens the conclusions; it just makes them reachable without a running start in advanced mathematics.