WEBVTT 00:00:00.058 --> 00:00:02.880 Here is a claim that ought to sound impossible. 00:00:03.193 --> 00:00:07.047 There is a question about computer programs, a completely precise question 00:00:07.047 --> 00:00:10.926 with a yes or no answer, that no computer program can answer. 00:00:11.029 --> 00:00:12.377 Not a slow one. 00:00:12.574 --> 00:00:15.651 Not one with more memory than any machine ever built. 00:00:15.848 --> 00:00:16.754 None. 00:00:18.406 --> 00:00:24.059 The question is this one. You are handed the text of a program P, and an input x. 00:00:24.142 --> 00:00:28.438 Does P eventually stop when you run it on x, or does it run forever? 00:00:29.238 --> 00:00:31.584 Call a program that answers that H. 00:00:31.708 --> 00:00:37.084 H always returns. It never runs forever itself, and it never says maybe. 00:00:37.281 --> 00:00:41.798 For every program and every input it hands back halts or loops, and it is right. 00:00:41.994 --> 00:00:45.676 The theorem we are heading for is that H does not exist. 00:00:46.472 --> 00:00:48.943 I want that to feel forced rather than clever, 00:00:49.026 --> 00:00:52.336 so we are going to practise the move first on something else. 00:00:52.532 --> 00:00:54.994 Something with no programs in it at all. 00:00:55.191 --> 00:00:56.562 The real numbers. 00:00:57.958 --> 00:01:03.090 Here is a list of real numbers between zero and one, written out as decimals. 00:01:03.194 --> 00:01:04.994 I have drawn four rows; 00:01:05.098 --> 00:01:07.305 you should imagine infinitely many. 00:01:07.408 --> 00:01:10.021 And here is the supposition we are going to break. 00:01:10.218 --> 00:01:12.088 This list is complete. 00:01:13.001 --> 00:01:16.029 Now I am going to build a number that is not on this list, 00:01:16.112 --> 00:01:19.039 and I am going to build it out of the list itself. 00:01:19.491 --> 00:01:21.834 Take the first digit of the first number. 00:01:21.917 --> 00:01:23.288 It is a one. 00:01:23.485 --> 00:01:27.131 Take the second digit of the second number, and that is a three. 00:01:27.928 --> 00:01:30.668 The third digit of the third number is a seven. 00:01:30.772 --> 00:01:33.443 The fourth digit of the fourth is a zero. 00:01:33.756 --> 00:01:36.831 Those four entries lie along the diagonal of the table, 00:01:36.914 --> 00:01:39.887 and the diagonal is where the whole argument lives. 00:01:40.799 --> 00:01:43.006 The rule for the new number is this. 00:01:43.203 --> 00:01:46.117 Take each diagonal digit and add one to it. 00:01:46.314 --> 00:01:50.143 If a diagonal digit happens to be a nine, write a one instead, 00:01:50.226 --> 00:01:54.093 so that we never finish with a tail of nines or a tail of zeros. 00:01:54.797 --> 00:01:58.049 One becomes two. Three becomes four. 00:01:58.152 --> 00:01:59.802 Seven becomes eight. 00:01:59.905 --> 00:02:01.938 And zero becomes one. 00:02:02.135 --> 00:02:03.993 Call the result d. 00:02:04.790 --> 00:02:09.501 So d is zero point two four eight one, and it carries on forever, 00:02:09.584 --> 00:02:12.429 one fresh digit for every row of the list. 00:02:12.626 --> 00:02:14.670 Now the only question that matters. 00:02:14.867 --> 00:02:16.493 Is d on the list? 00:02:17.196 --> 00:02:18.555 It cannot be the first number, 00:02:18.555 --> 00:02:22.863 because d was built to differ from the first number in the first decimal place. 00:02:22.966 --> 00:02:25.011 Two, not one. 00:02:25.807 --> 00:02:29.532 It cannot be the second number either, because they differ in the second place. 00:02:29.615 --> 00:02:31.065 Four against three. 00:02:31.148 --> 00:02:35.247 And not the third, and not the fourth, for exactly the same reason. 00:02:35.556 --> 00:02:40.767 And for any row number n at all, d differs from row n in the n-th decimal place, 00:02:40.850 --> 00:02:44.148 because that is precisely what the rule was built to do. 00:02:44.345 --> 00:02:48.118 So d is a real number between zero and one, missing from a list 00:02:48.118 --> 00:02:51.764 that was supposed to contain every real number between zero and one. 00:02:52.816 --> 00:02:56.614 That is a contradiction, so the supposition was wrong. 00:02:56.810 --> 00:02:59.504 No list of real numbers can be complete. 00:02:59.608 --> 00:03:03.104 There are strictly more reals than there are rows to put them in. 00:03:04.500 --> 00:03:06.867 Strip that argument down to its bones, 00:03:06.950 --> 00:03:10.550 because we are about to run it again on something completely different. 00:03:10.747 --> 00:03:15.844 Step one, assume a complete table, with one row for every object. 00:03:16.041 --> 00:03:19.408 Step two, read the entries down the diagonal. 00:03:20.205 --> 00:03:25.045 Step three, build a new object that disagrees with row n at position n, 00:03:25.128 --> 00:03:27.253 for every n at once. 00:03:27.868 --> 00:03:31.837 Step four, notice that this new object cannot be any row at all, 00:03:31.920 --> 00:03:34.057 so the table was never complete. 00:03:34.667 --> 00:03:37.408 The diagonal is doing all of the work there. 00:03:37.721 --> 00:03:41.471 It is the one place where a single new object can be made to disagree 00:03:41.471 --> 00:03:45.814 with every row of an infinite table, using just one entry from each row. 00:03:46.928 --> 00:03:48.577 Start with programs. 00:03:48.774 --> 00:03:51.267 A program is a finite string of characters, 00:03:51.351 --> 00:03:54.719 and that is the only fact about programs we are going to need. 00:03:54.823 --> 00:04:00.010 So write out every finite string, shortest first, alphabetically within each length, 00:04:00.094 --> 00:04:05.470 and cross out every string that is not a valid program. What survives is a list. 00:04:06.266 --> 00:04:10.690 P one, P two, P three, P four, and on forever. 00:04:11.142 --> 00:04:15.435 Every program you will ever write sits on it, at a definite finite position, 00:04:15.519 --> 00:04:17.598 and nothing sits on it twice. 00:04:17.911 --> 00:04:21.937 Unlike Cantor's list of reals, this list is not a supposition. 00:04:22.021 --> 00:04:23.856 We can actually construct it. 00:04:24.560 --> 00:04:26.728 Inputs are finite strings too, 00:04:26.812 --> 00:04:30.772 so there is nothing to stop us handing a program the text of another program. 00:04:30.876 --> 00:04:32.676 Or the text of itself. 00:04:32.872 --> 00:04:37.180 So along the top I will put that same list again, this time as inputs. 00:04:37.605 --> 00:04:40.194 That gives us a table. The entry in row i, 00:04:40.194 --> 00:04:45.114 column j records what program P i does when you run it on the text of P j. 00:04:45.198 --> 00:04:46.612 It either stops eventually, 00:04:46.696 --> 00:04:50.969 and I will write a one, or it runs forever, and I will write a zero. 00:04:51.673 --> 00:04:53.160 Here is a corner of it. 00:04:53.356 --> 00:04:58.698 Row P one, run on the text of P one, stops, so that entry is a one. 00:04:58.894 --> 00:05:02.843 Row P one on P two runs forever, so a zero. 00:05:03.039 --> 00:05:05.466 Fill in the rest of the table the same way. 00:05:06.170 --> 00:05:08.051 Every cell has an entry. 00:05:08.248 --> 00:05:10.629 Not an entry we know: an entry. 00:05:10.825 --> 00:05:15.838 Run P three on its own text and either it stops or it does not, and that is settled, 00:05:15.922 --> 00:05:18.651 whether or not anybody ever finds out which. 00:05:18.848 --> 00:05:22.378 The table is completely determined before we ask how to compute it. 00:05:23.290 --> 00:05:25.520 Now assume the decider exists. 00:05:25.717 --> 00:05:27.978 H takes a program and an input, 00:05:28.062 --> 00:05:31.952 and returns the correct entry of this table, in finite time. 00:05:32.404 --> 00:05:35.981 Feed it a row and a column and it hands you back that cell. 00:05:36.177 --> 00:05:37.293 Always. 00:05:38.345 --> 00:05:41.364 That is exactly what decidable means. 00:05:41.817 --> 00:05:45.204 Not that the answer exists, which we have already agreed it does, 00:05:45.288 --> 00:05:50.118 but that one single program computes it, for every pair, and finishes. 00:05:50.431 --> 00:05:54.449 If H exists, this whole infinite table is on tap. 00:05:55.246 --> 00:05:57.069 Now look at the diagonal. 00:05:57.265 --> 00:06:00.458 Each of these cells asks what one program does when you run it 00:06:00.458 --> 00:06:02.421 on a copy of its own text. 00:06:02.618 --> 00:06:08.272 P one on itself, P two on itself, P three on itself, and so on down. 00:06:09.069 --> 00:06:11.775 There is nothing paradoxical about that yet. 00:06:11.971 --> 00:06:13.675 A program is a string, 00:06:13.759 --> 00:06:17.204 and a string is a perfectly ordinary thing to feed to a program. 00:06:17.288 --> 00:06:19.681 Compilers do it every day of the week. 00:06:20.659 --> 00:06:25.138 And now we build the contrary program, exactly the way Cantor built his number. 00:06:25.222 --> 00:06:29.669 Call it D. D takes one input, a program P, and the first thing 00:06:29.669 --> 00:06:33.641 it does is ask H whether P halts when you run it on its own text. 00:06:34.437 --> 00:06:37.480 And then D does the opposite of whatever it hears. 00:06:37.676 --> 00:06:42.705 If H says P halts on itself, D deliberately drops into an infinite loop. 00:06:42.809 --> 00:06:46.850 If H says P loops on itself, D stops immediately. 00:06:47.646 --> 00:06:52.427 D is not exotic. It is a call and a branch, perhaps five lines long. 00:06:52.511 --> 00:06:55.886 If the decider exists then this program exists too, 00:06:55.970 --> 00:06:59.130 and there is no sleight of hand anywhere in the construction. 00:06:59.439 --> 00:07:04.846 So let us fill in D's row. Column one asks what D does on the text of P one. 00:07:04.930 --> 00:07:06.913 The diagonal entry there is a one, 00:07:06.997 --> 00:07:11.758 meaning P one halts on itself, so D does the opposite and runs forever. 00:07:11.954 --> 00:07:13.325 I write a zero. 00:07:14.122 --> 00:07:20.357 Column two: the diagonal entry is a one again, so D loops, and I write a zero. 00:07:20.658 --> 00:07:23.793 Column three: another one, so another zero. 00:07:24.094 --> 00:07:27.006 Column four: the diagonal entry is a zero, 00:07:27.090 --> 00:07:30.910 P four never stops on its own text, so D halts. 00:07:31.324 --> 00:07:33.031 And there is the pattern. 00:07:33.622 --> 00:07:37.149 D's row is the diagonal with every entry flipped. 00:07:37.233 --> 00:07:42.815 Where the diagonal says one, D says zero, and where it says zero, D says one. 00:07:42.899 --> 00:07:47.230 D disagrees with the diagonal everywhere, and it does so deliberately. 00:07:48.627 --> 00:07:50.960 Now the same question Cantor asked. 00:07:51.157 --> 00:07:52.806 Is D on the list? 00:07:53.003 --> 00:07:57.508 It has to be. D is a program, and the list contains every program, 00:07:57.508 --> 00:07:59.424 so D appears on it somewhere. 00:07:59.621 --> 00:08:02.861 Call its position k. D is P k. 00:08:03.286 --> 00:08:05.562 That means two things at the same time. 00:08:05.759 --> 00:08:10.961 D has a row of its own, row k, and that row is the one we have just filled in. 00:08:11.157 --> 00:08:12.690 And D has a column of its own, 00:08:12.690 --> 00:08:17.370 column k, because the text of D is a legitimate input like any other. 00:08:18.166 --> 00:08:20.791 So look at where that row meets that column. 00:08:20.987 --> 00:08:23.922 Cell k, k. It sits on the diagonal, 00:08:24.006 --> 00:08:28.419 and it sits in D's row, and it has to answer exactly one question. 00:08:28.871 --> 00:08:32.088 Does D halt when you run it on a copy of its own text? 00:08:32.884 --> 00:08:34.789 Suppose the answer is one. 00:08:35.102 --> 00:08:37.378 D halts on its own text. 00:08:37.830 --> 00:08:39.746 But D's row was built to disagree 00:08:39.746 --> 00:08:45.099 with the diagonal, and this cell is on the diagonal, so D's row says zero there. 00:08:45.295 --> 00:08:47.874 D halts and D does not halt. 00:08:48.357 --> 00:08:51.109 Suppose instead the answer is zero. 00:08:51.306 --> 00:08:56.574 Then H reports that D loops on its own text, so D, by its own definition, 00:08:56.658 --> 00:08:59.143 does the opposite and halts immediately. 00:08:59.246 --> 00:09:02.753 Which makes the cell a one after all. Again both. 00:09:03.295 --> 00:09:04.917 And there is no third option. 00:09:05.001 --> 00:09:09.805 The cell is a one or it is a zero, because the run either stops or it does not, 00:09:09.889 --> 00:09:12.452 and we have just shown that both are impossible. 00:09:12.536 --> 00:09:15.997 Cell k, k is not equal to itself. 00:09:17.049 --> 00:09:21.577 So one of our assumptions is false, and it is worth checking which ones we made. 00:09:21.762 --> 00:09:23.699 That programs can be listed: 00:09:23.783 --> 00:09:26.268 true, we constructed the list. 00:09:26.372 --> 00:09:28.439 That every cell has an entry: 00:09:28.635 --> 00:09:32.120 true, every run either stops or it does not. 00:09:32.316 --> 00:09:34.484 That D can be built from H: 00:09:34.568 --> 00:09:37.123 true, it is a call and a branch. 00:09:38.636 --> 00:09:42.561 The only thing left is H, so H is what has to go. 00:09:42.758 --> 00:09:46.795 There is no program that takes an arbitrary program and an arbitrary input 00:09:46.879 --> 00:09:51.420 and always reports, correctly and in finite time, whether it halts. 00:09:51.524 --> 00:09:53.846 The halting problem is undecidable. 00:09:54.931 --> 00:09:57.822 Before we go any further I want to separate two things 00:09:57.822 --> 00:10:00.005 that get run together constantly. 00:10:00.109 --> 00:10:05.518 Undecidable does not mean hard. It does not mean expensive, or exponential, 00:10:05.601 --> 00:10:07.830 or out of reach of current hardware. 00:10:08.027 --> 00:10:09.897 Compare two questions. 00:10:10.601 --> 00:10:12.087 Here is the first. 00:10:12.284 --> 00:10:15.420 Does this program halt within a billion steps? 00:10:15.616 --> 00:10:19.831 That question is decidable, and the algorithm for it is embarrassing. 00:10:20.144 --> 00:10:22.153 Simulate a billion steps. 00:10:22.350 --> 00:10:24.719 If it stopped, say yes. 00:10:25.032 --> 00:10:27.471 If it is still running, say no. 00:10:28.267 --> 00:10:29.906 That may take a week. 00:10:30.102 --> 00:10:33.063 It may take longer than the universe has been going. 00:10:33.260 --> 00:10:34.849 None of that matters here. 00:10:34.932 --> 00:10:36.313 The procedure is finite, 00:10:36.313 --> 00:10:39.844 it always terminates, and it always gives the correct answer. 00:10:40.156 --> 00:10:42.502 That question is about cost. 00:10:43.299 --> 00:10:44.762 Here is the second. 00:10:45.075 --> 00:10:47.699 Does this program halt, ever? 00:10:48.314 --> 00:10:52.982 Run the very same procedure. Simulate a billion steps, and it is still running. 00:10:53.573 --> 00:10:55.072 What do you conclude? 00:10:55.257 --> 00:10:56.836 Nothing whatsoever. 00:10:57.010 --> 00:10:59.031 It might stop on the next step. 00:11:00.222 --> 00:11:04.019 There is no number of steps at which silence turns into an answer. 00:11:04.610 --> 00:11:07.490 Simulation buys you exactly one thing. 00:11:07.687 --> 00:11:11.043 If the program halts, you will eventually find out. 00:11:11.240 --> 00:11:16.372 If it does not, you wait forever, and waiting forever is not an algorithm. 00:11:17.424 --> 00:11:20.199 Here is what that feels like from the inside. 00:11:20.396 --> 00:11:23.796 This program takes a whole number and repeats one rule. 00:11:23.879 --> 00:11:26.236 If the number is even, halve it. 00:11:26.433 --> 00:11:29.510 If it is odd, triple it and add one. 00:11:29.707 --> 00:11:31.507 Stop when you reach one. 00:11:32.211 --> 00:11:35.439 Start it at twenty seven and follow the value along. 00:11:35.636 --> 00:11:38.769 It wanders up and down for a hundred and eleven steps, 00:11:38.852 --> 00:11:41.300 climbing above nine thousand on the way, 00:11:41.383 --> 00:11:43.891 and then it falls to one and stops. 00:11:44.688 --> 00:11:46.163 Now the question. 00:11:46.360 --> 00:11:49.971 Is there a starting number for which this program never stops? 00:11:50.423 --> 00:11:55.077 Nobody knows. It has been checked for every start below two to the sixty eight, 00:11:55.160 --> 00:11:57.111 and checking is not proving. 00:11:57.907 --> 00:12:01.066 And notice how little our theorem actually claims. 00:12:01.263 --> 00:12:04.607 It does not say we cannot analyse programs. 00:12:04.711 --> 00:12:08.752 Compilers prove termination of particular loops all day long. 00:12:08.948 --> 00:12:13.091 It says no single procedure works for every program and every input, 00:12:13.174 --> 00:12:15.752 and one bad case is enough to sink it. 00:12:17.149 --> 00:12:19.402 So keep the two ideas apart. 00:12:19.599 --> 00:12:22.792 Complexity asks how long a procedure takes. 00:12:22.989 --> 00:12:26.902 Computability asks whether a procedure exists at all. 00:12:27.354 --> 00:12:32.289 Our proof never mentioned time, or memory, or the speed of the machine. 00:12:33.201 --> 00:12:37.718 Give H a faster processor, and D still contradicts itself. 00:12:38.333 --> 00:12:43.512 Give it a thousand years and unlimited memory, and D still contradicts itself. 00:12:43.964 --> 00:12:47.308 The obstruction is logical, not economic. 00:12:48.326 --> 00:12:50.986 One theorem on its own is a curiosity. 00:12:51.438 --> 00:12:55.873 What makes this a technique is that you only ever have to run the diagonal once. 00:12:56.070 --> 00:12:58.355 Everything after it arrives by reduction, 00:12:58.439 --> 00:13:01.411 and I want to do one so that you can see the shape of it. 00:13:02.208 --> 00:13:04.136 Here is a second question. 00:13:04.332 --> 00:13:08.188 Given a machine M, does M halt on every input? 00:13:08.384 --> 00:13:10.544 Not on one particular input. 00:13:10.741 --> 00:13:12.181 On all of them. 00:13:12.378 --> 00:13:14.674 That is called the totality problem, 00:13:14.758 --> 00:13:18.811 and it is the question a compiler would love to answer about your loops. 00:13:19.607 --> 00:13:22.275 It looks harder than halting rather than easier, 00:13:22.359 --> 00:13:25.552 since it asks about infinitely many runs at once. 00:13:25.865 --> 00:13:28.745 Suppose all the same that it is decidable. 00:13:29.197 --> 00:13:32.701 So there is a program T which takes a machine and always tells you, 00:13:32.785 --> 00:13:36.674 correctly and in finite time, whether it halts on everything. 00:13:38.326 --> 00:13:40.100 Watch what we can do with T. 00:13:40.184 --> 00:13:43.130 Take any program P and any input x, 00:13:43.214 --> 00:13:46.582 the pair we would like to answer the halting question about. 00:13:47.382 --> 00:13:51.783 Out of those two pieces we build a new machine, and here is the machine. 00:13:52.580 --> 00:13:57.677 It takes an input y, throws y away without looking at it, and runs P on x. 00:13:57.874 --> 00:13:59.535 That is the whole of it. 00:13:59.848 --> 00:14:03.990 Building the thing is pure text manipulation: you are pasting P and x 00:14:04.074 --> 00:14:07.058 into a template, and that always finishes. 00:14:07.855 --> 00:14:09.361 So what does this machine do? 00:14:09.445 --> 00:14:13.634 Because it ignores its input, it behaves identically on every input, 00:14:13.718 --> 00:14:18.595 which leaves only two cases, and they are exactly the two cases we care about. 00:14:19.136 --> 00:14:24.465 If P halts on x, then M halts on y, whatever y happens to be. 00:14:24.662 --> 00:14:30.499 So M halts on every input, which is to say M is total. If P runs forever on x, 00:14:30.583 --> 00:14:34.961 then M runs forever on every input, so M halts on nothing at all. 00:14:35.746 --> 00:14:38.486 So hand M to the totality decider. 00:14:38.671 --> 00:14:41.819 If T says yes, then P halts on x. 00:14:41.992 --> 00:14:45.581 If T says no, then P does not halt on x. 00:14:45.893 --> 00:14:50.515 Either way you have a correct answer to the halting question, in finite time. 00:14:51.311 --> 00:14:56.719 Now put the two pieces inside one box. That box takes a program and an input, 00:14:56.803 --> 00:15:01.053 builds M, asks T, and reports whether the program halts. 00:15:01.250 --> 00:15:04.397 Correctly, always, in finite time. 00:15:04.500 --> 00:15:06.150 That box is H. 00:15:06.633 --> 00:15:10.485 And we spent the last ten minutes proving that H cannot exist. 00:15:10.569 --> 00:15:14.839 So the assumption that manufactured it is the thing that is false. 00:15:14.923 --> 00:15:19.777 There is no totality decider, and the totality problem is undecidable too. 00:15:21.080 --> 00:15:23.167 Notice what we did not have to do there. 00:15:23.251 --> 00:15:28.624 We did not diagonalise again. We took the one impossible object we already had, 00:15:28.708 --> 00:15:31.829 and showed that a totality decider would manufacture it, 00:15:31.913 --> 00:15:35.385 so the totality decider goes the same way the first one went. 00:15:36.089 --> 00:15:39.503 That is a reduction, and it is the standard move. 00:15:39.699 --> 00:15:42.556 Does this machine ever print the word hello? 00:15:42.660 --> 00:15:45.424 Do these two programs compute the same function? 00:15:45.528 --> 00:15:48.509 Is there any input at all that this machine accepts? 00:15:48.593 --> 00:15:50.649 Same argument, every time. 00:15:51.445 --> 00:15:54.566 Almost every interesting question about what a program does, 00:15:54.650 --> 00:15:58.795 as opposed to what its text looks like, turns out to be undecidable. 00:15:58.992 --> 00:16:01.288 And all of it traces back to one table, 00:16:01.372 --> 00:16:05.320 one flipped row, and one cell that cannot decide what it is.