A First Taste of Algorithms · Epilogue: The Edge of the Map

The barber who shaves himself

The argument is a descendant of an old paradox. A town has one barber, who shaves exactly those men who do not shave themselves. Does the barber shave himself? If he does, then he is a man who shaves himself, so by the rule the barber does not shave him — contradiction. If he does not, then he is a man who does not shave himself, so by the rule the barber does shave him — contradiction. There is no consistent answer. The town, as described, cannot exist.

Turing built that barber out of programs. Suppose, for contradiction, the halt-checker exists: a program HALTS(P, x) that always stops and correctly returns yes if program P halts on input x, no if it loops forever. From it, build a second program — call it TROUBLE — that takes a single program P as input and does this:

ask HALTS(P, P) — does P halt when fed its own code as input? if the answer is yes, deliberately loop forever; if the answer is no, immediately stop.

TROUBLE does the opposite of whatever the halt-checker predicts. Now ask the question that destroys the town. Run TROUBLE on its own code. Does TROUBLE(TROUBLE) halt?

• Suppose it halts. It halts only if, inside, HALTS(TROUBLE, TROUBLE) returned no — i.e. the halt-checker predicted it runs forever. The checker was wrong.
• Suppose it runs forever. It loops only if HALTS(TROUBLE, TROUBLE) returned yes — i.e. the checker predicted it halts. The checker was wrong.

Either way the halt-checker gives the wrong answer about TROUBLE(TROUBLE). But the halt-checker was assumed never to be wrong. The assumption cannot stand. No halt-checker exists — not “none has been found,” not “none is fast enough,” but none is possible, ever, on any machine, by any mind. The work cannot be refused because it cannot be done.

Deeper water: this is Chapter 6’s fence, grown infinite

Look at the shape of what just happened. Chapter 6 proved no comparison sort beats n log n by counting: n! distinct situations, too few questions to tell them apart. Chapter 1 fenced the guessing game the same way. This is that argument’s furthest reach — a diagonal argument, the technique Georg Cantor invented in 1891 to prove some infinities are larger than others. Imagine an infinite table: one row per program, one column per input, each cell marked “halts” or “loops.” TROUBLE is built to disagree with the table’s diagonal — to differ from program 1 on input 1, program 2 on input 2, program k on input k, forever. So TROUBLE cannot be any row of the table; it differs from each at the diagonal. Yet TROUBLE is a perfectly good program — it should be some row. Contradiction, built by walking down the diagonal and flipping every entry. The same diagonal flip proves there are more real numbers than whole numbers, more functions than programs to compute them, more truths than proofs. It is the single most powerful idea about the limits of systems, and you have now seen it draw a fence around computation itself.

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