A First Taste of Algorithms

Epilogue: The Edge of the Map

✦ ✦ ✦

No problems. No lab. Written to be over your head now and exactly right later.

Nine chapters asked two questions of one algorithm after another — is it right? what does it cost? — and answered them, every time. This last chapter is about the questions that do not get answered. Not because the book is elementary, though it is, but because no one on Earth yet knows the answers, or because the answers are no — there are problems no algorithm will ever solve, and the proof that they exist is one of the most beautiful things a human mind has produced. The map you have been drawing has edges. Standing at them, looking out, is the best view in the subject.

Work that cannot be refused

The whole book was a campaign of refusal: an algorithm is a way of not doing most of the work, and chapter after chapter found the work that could be skipped. So a fair question — the kind that ends some inquiries and opens others — is whether refusal has a limit. Is there work that cannot be skipped, a problem so hard that no clever trick, no idea however deep, no machine however fast, will ever solve it?

There is, and the first example is not exotic. It is a question about programs themselves.

You met it in Chapter 3, and were told to hold it. Checking that your recursion terminates was easy — it shrank toward a floor. But could there be a single algorithm — call it the halt-checker — that reads any program, together with its input, and correctly answers one yes-or-no question: does this program eventually stop, or does it run forever? Such a thing would be priceless. It would catch every infinite loop before it ran, prove software correct, settle open mathematical conjectures by running a search and asking whether it ever halts. Surely, with enough cleverness, it can be built.

It cannot. And here is the proof — the halting problem, proved by Alan Turing in 1936, before there were computers to run the programs it is about.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses