The Halting Problem Is Undecidable

Here is a claim that ought to sound impossible. There is a question about computer programs, a completely precise question with a yes or no answer, that no computer program can answer. Not a slow one. Not one with more memory than any machine ever built. None. The question is this one. You are handed the text of a program P, and an input x. Does P eventually stop when you run it on x, or does it run forever? Call a program that answers that H. H always returns. It never runs forever itself, and it never says maybe. For every program and every input it hands back halts or loops, and it is right. The theorem we are heading for is that H does not exist. I want that to feel forced rather than clever, so we are going to practise the move first on something else. Something with no programs in it at all. The real numbers. Here is a list of real numbers between zero and one, written out as decimals. I have drawn four rows; you should imagine infinitely many. And here is the supposition we are going to break. This list is complete. Now I am going to build a number that is not on this list, and I am going to build it out of the list itself. Take the first digit of the first number. It is a one. Take the second digit of the second number, and that is a three. The third digit of the third number is a seven. The fourth digit of the fourth is a zero. Those four entries lie along the diagonal of the table, and the diagonal is where the whole argument lives. The rule for the new number is this. Take each diagonal digit and add one to it. If a diagonal digit happens to be a nine, write a one instead, so that we never finish with a tail of nines or a tail of zeros. One becomes two. Three becomes four. Seven becomes eight. And zero becomes one. Call the result d. So d is zero point two four eight one, and it carries on forever, one fresh digit for every row of the list. Now the only question that matters. Is d on the list? It cannot be the first number, because d was built to differ from the first number in the first decimal place. Two, not one. It cannot be the second number either, because they differ in the second place. Four against three. And not the third, and not the fourth, for exactly the same reason. And for any row number n at all, d differs from row n in the n-th decimal place, because that is precisely what the rule was built to do. So d is a real number between zero and one, missing from a list that was supposed to contain every real number between zero and one. That is a contradiction, so the supposition was wrong. No list of real numbers can be complete. There are strictly more reals than there are rows to put them in. Strip that argument down to its bones, because we are about to run it again on something completely different. Step one, assume a complete table, with one row for every object. Step two, read the entries down the diagonal. Step three, build a new object that disagrees with row n at position n, for every n at once. Step four, notice that this new object cannot be any row at all, so the table was never complete. The diagonal is doing all of the work there. It is the one place where a single new object can be made to disagree with every row of an infinite table, using just one entry from each row.

Start with programs. A program is a finite string of characters, and that is the only fact about programs we are going to need. So write out every finite string, shortest first, alphabetically within each length, and cross out every string that is not a valid program. What survives is a list. P one, P two, P three, P four, and on forever. Every program you will ever write sits on it, at a definite finite position, and nothing sits on it twice. Unlike Cantor's list of reals, this list is not a supposition. We can actually construct it. Inputs are finite strings too, so there is nothing to stop us handing a program the text of another program. Or the text of itself. So along the top I will put that same list again, this time as inputs. That gives us a table. The entry in row i, column j records what program P i does when you run it on the text of P j. It either stops eventually, and I will write a one, or it runs forever, and I will write a zero. Here is a corner of it. Row P one, run on the text of P one, stops, so that entry is a one. Row P one on P two runs forever, so a zero. Fill in the rest of the table the same way. Every cell has an entry. Not an entry we know: an entry. Run P three on its own text and either it stops or it does not, and that is settled, whether or not anybody ever finds out which. The table is completely determined before we ask how to compute it. Now assume the decider exists. H takes a program and an input, and returns the correct entry of this table, in finite time. Feed it a row and a column and it hands you back that cell. Always. That is exactly what decidable means. Not that the answer exists, which we have already agreed it does, but that one single program computes it, for every pair, and finishes. If H exists, this whole infinite table is on tap. Now look at the diagonal. Each of these cells asks what one program does when you run it on a copy of its own text. P one on itself, P two on itself, P three on itself, and so on down. There is nothing paradoxical about that yet. A program is a string, and a string is a perfectly ordinary thing to feed to a program. Compilers do it every day of the week. And now we build the contrary program, exactly the way Cantor built his number. Call it D. D takes one input, a program P, and the first thing it does is ask H whether P halts when you run it on its own text. And then D does the opposite of whatever it hears. If H says P halts on itself, D deliberately drops into an infinite loop. If H says P loops on itself, D stops immediately. D is not exotic. It is a call and a branch, perhaps five lines long. If the decider exists then this program exists too, and there is no sleight of hand anywhere in the construction. So let us fill in D's row. Column one asks what D does on the text of P one. The diagonal entry there is a one, meaning P one halts on itself, so D does the opposite and runs forever. I write a zero. Column two: the diagonal entry is a one again, so D loops, and I write a zero. Column three: another one, so another zero. Column four: the diagonal entry is a zero, P four never stops on its own text, so D halts. And there is the pattern. D's row is the diagonal with every entry flipped. Where the diagonal says one, D says zero, and where it says zero, D says one. D disagrees with the diagonal everywhere, and it does so deliberately. Now the same question Cantor asked. Is D on the list? It has to be. D is a program, and the list contains every program, so D appears on it somewhere. Call its position k. D is P k. That means two things at the same time. D has a row of its own, row k, and that row is the one we have just filled in. And D has a column of its own, column k, because the text of D is a legitimate input like any other. So look at where that row meets that column. Cell k, k. It sits on the diagonal, and it sits in D's row, and it has to answer exactly one question. Does D halt when you run it on a copy of its own text? Suppose the answer is one. D halts on its own text. But D's row was built to disagree with the diagonal, and this cell is on the diagonal, so D's row says zero there. D halts and D does not halt. Suppose instead the answer is zero. Then H reports that D loops on its own text, so D, by its own definition, does the opposite and halts immediately. Which makes the cell a one after all. Again both. And there is no third option. The cell is a one or it is a zero, because the run either stops or it does not, and we have just shown that both are impossible. Cell k, k is not equal to itself. So one of our assumptions is false, and it is worth checking which ones we made. That programs can be listed: true, we constructed the list. That every cell has an entry: true, every run either stops or it does not. That D can be built from H: true, it is a call and a branch. The only thing left is H, so H is what has to go. There is no program that takes an arbitrary program and an arbitrary input and always reports, correctly and in finite time, whether it halts. The halting problem is undecidable.

Before we go any further I want to separate two things that get run together constantly. Undecidable does not mean hard. It does not mean expensive, or exponential, or out of reach of current hardware. Compare two questions. Here is the first. Does this program halt within a billion steps? That question is decidable, and the algorithm for it is embarrassing. Simulate a billion steps. If it stopped, say yes. If it is still running, say no. That may take a week. It may take longer than the universe has been going. None of that matters here. The procedure is finite, it always terminates, and it always gives the correct answer. That question is about cost. Here is the second. Does this program halt, ever? Run the very same procedure. Simulate a billion steps, and it is still running. What do you conclude? Nothing whatsoever. It might stop on the next step. There is no number of steps at which silence turns into an answer. Simulation buys you exactly one thing. If the program halts, you will eventually find out. If it does not, you wait forever, and waiting forever is not an algorithm. Here is what that feels like from the inside. This program takes a whole number and repeats one rule. If the number is even, halve it. If it is odd, triple it and add one. Stop when you reach one. Start it at twenty seven and follow the value along. It wanders up and down for a hundred and eleven steps, climbing above nine thousand on the way, and then it falls to one and stops. Now the question. Is there a starting number for which this program never stops? Nobody knows. It has been checked for every start below two to the sixty eight, and checking is not proving. And notice how little our theorem actually claims. It does not say we cannot analyse programs. Compilers prove termination of particular loops all day long. It says no single procedure works for every program and every input, and one bad case is enough to sink it. So keep the two ideas apart. Complexity asks how long a procedure takes. Computability asks whether a procedure exists at all. Our proof never mentioned time, or memory, or the speed of the machine. Give H a faster processor, and D still contradicts itself. Give it a thousand years and unlimited memory, and D still contradicts itself. The obstruction is logical, not economic.

One theorem on its own is a curiosity. What makes this a technique is that you only ever have to run the diagonal once. Everything after it arrives by reduction, and I want to do one so that you can see the shape of it. Here is a second question. Given a machine M, does M halt on every input? Not on one particular input. On all of them. That is called the totality problem, and it is the question a compiler would love to answer about your loops. It looks harder than halting rather than easier, since it asks about infinitely many runs at once. Suppose all the same that it is decidable. So there is a program T which takes a machine and always tells you, correctly and in finite time, whether it halts on everything. Watch what we can do with T. Take any program P and any input x, the pair we would like to answer the halting question about. Out of those two pieces we build a new machine, and here is the machine. It takes an input y, throws y away without looking at it, and runs P on x. That is the whole of it. Building the thing is pure text manipulation: you are pasting P and x into a template, and that always finishes. So what does this machine do? Because it ignores its input, it behaves identically on every input, which leaves only two cases, and they are exactly the two cases we care about. If P halts on x, then M halts on y, whatever y happens to be. So M halts on every input, which is to say M is total. If P runs forever on x, then M runs forever on every input, so M halts on nothing at all. So hand M to the totality decider. If T says yes, then P halts on x. If T says no, then P does not halt on x. Either way you have a correct answer to the halting question, in finite time. Now put the two pieces inside one box. That box takes a program and an input, builds M, asks T, and reports whether the program halts. Correctly, always, in finite time. That box is H. And we spent the last ten minutes proving that H cannot exist. So the assumption that manufactured it is the thing that is false. There is no totality decider, and the totality problem is undecidable too. Notice what we did not have to do there. We did not diagonalise again. We took the one impossible object we already had, and showed that a totality decider would manufacture it, so the totality decider goes the same way the first one went. That is a reduction, and it is the standard move. Does this machine ever print the word hello? Do these two programs compute the same function? Is there any input at all that this machine accepts? Same argument, every time. Almost every interesting question about what a program does, as opposed to what its text looks like, turns out to be undecidable. And all of it traces back to one table, one flipped row, and one cell that cannot decide what it is.