# The Halting Problem Is Undecidable > No program can decide whether an arbitrary program halts, and this lecture builds that result until it feels forced rather than clever. We warm up with Cantor's diagonal argument on the real numbers, so the shape of the technique is familiar before it matters. Then we lay out the infinite table of programs against inputs, assume a halting decider fills in every cell, and build the contrary program that consults the decider and deliberately does the opposite. The contradiction lands on the diagonal cell where it has to. We then separate undecidability from mere expense, using a bounded halting question and an open problem about a three line program, and close by reducing the halting problem to totality, so that the technique is visibly reusable rather than a single trick. - Canonical watch page: [The Halting Problem Is Undecidable](https://academa.ai/lectures/halting-problem-undecidability) - Publisher: [Academa, Inc.](https://academa.ai) - Subject: Computer Science - Published: 2026-08-28T18:45:36.643Z - Updated: 2026-08-28T18:45:36.643Z - Duration: PT992S (16 minutes 32 seconds) - Chapters: 4 - Views: 0 - Language: en-US - Access: Free - Video stream: [HLS content](https://academa.ai/media/l/01M14TXEZX293E70GEK3H8CACX/0/dark/master.m3u8) - Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TXEZX293E70GEK3H8CACX/0/semantic.json) - Thumbnail: [Image](https://academa.ai/media/l/01M14TXEZX293E70GEK3H8CACX/0/dark/poster.jpg) ## Description Cantor's diagonal, the table of programs against inputs, and the contrary program that proves no halting decider can exist. ## Chapters - [00:00–03:51.284 · A List That Cannot Be Complete](https://academa.ai/lectures/halting-problem-undecidability?t=0) - [03:51.284–10:27.343 · The Table of Programs](https://academa.ai/lectures/halting-problem-undecidability?t=231.28431249999997) - [10:27.343–13:10.742 · Undecidable Is Not the Same as Expensive](https://academa.ai/lectures/halting-problem-undecidability?t=627.3433333333335) - [13:10.742–16:32 · One More, by Reduction](https://academa.ai/lectures/halting-problem-undecidability?t=790.7419375000002) ## Transcript ### [00:00 · A List That Cannot Be Complete](https://academa.ai/lectures/halting-problem-undecidability?t=0) 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. ### [03:51.284 · The Table of Programs](https://academa.ai/lectures/halting-problem-undecidability?t=231.28431249999997) 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. ### [10:27.343 · Undecidable Is Not the Same as Expensive](https://academa.ai/lectures/halting-problem-undecidability?t=627.3433333333335) 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. ### [13:10.742 · One More, by Reduction](https://academa.ai/lectures/halting-problem-undecidability?t=790.7419375000002) 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. ## About Academa, Inc. Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need. ## Complete audiovisual record Immutable source: [semantic.json](https://academa.ai/media/l/01M14TXEZX293E70GEK3H8CACX/0/semantic.json) Record version: 1. Render attempt: 0. ### How to read this timeline Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video. ### Scene 1: [A List That Cannot Be Complete](https://academa.ai/lectures/halting-problem-undecidability?t=0) Span: 00:00–03:51.284 (0s–231.28431249999997s). #### Objects - card: a Title that says "Theory of Computation — The Halting Problem Is Undecidable" - cells: a Math \[text\] that says "$1$" drawn in sheet - cells\_10: a Math \[text\] that says "$3$" drawn in sheet - cells\_11: a Math \[text\] that says "$7$" drawn in sheet - cells\_12: a Math \[text\] that says "$0$" drawn in sheet - cells\_13: a Math \[text\] that says "$7$" drawn in sheet - cells\_14: a Math \[text\] that says "$1$" drawn in sheet - cells\_15: a Math \[text\] that says "$0$" drawn in sheet - cells\_16: a Math \[text\] that says "$5$" drawn in sheet - cells\_17: a Math \[text\] that says "$0$" drawn in sheet - cells\_18: a Math \[text\] that says "$0$" drawn in sheet - cells\_19: a Math \[text\] that says "$0$" drawn in sheet - cells\_2: a Math \[text\] that says "$4$" drawn in sheet - cells\_20: a Math \[text\] that says "$0$" drawn in sheet - cells\_3: a Math \[text\] that says "$1$" drawn in sheet - cells\_4: a Math \[text\] that says "$5$" drawn in sheet - cells\_5: a Math \[text\] that says "$9$" drawn in sheet - cells\_6: a Math \[text\] that says "$3$" drawn in sheet - cells\_7: a Math \[text\] that says "$3$" drawn in sheet - cells\_8: a Math \[text\] that says "$3$" drawn in sheet - cells\_9: a Math \[text\] that says "$3$" drawn in sheet - claim: a Text \[text\] that says "Every real number between 0 and 1 is somewhere on this list." - decider: a Math \[text\] that says "$H(P, x) = upright("halts") quad upright("or") quad upright("loops")$" - divider: a Line \[gray\] drawn in sheet (start=(0.7, 1.55), end=(7.8, 1.55), dashed=True) - guide: a Line \[yellow\] drawn in sheet (start=(2.55, 5.85), end=(5.95, 2.45), dashed=True) - head\_check: a Heading that says "Is the New Number on the List?" - head\_list: a Heading that says "Suppose the List Is Complete" - head\_plan: a Heading that says "The Question We Are Asking" - head\_shape: a Heading that says "The Shape of the Argument" - m1: a Math \[text\] that says "$d eq.not r\_1$" - m2: a Math \[text\] that says "$d eq.not r\_2$" - m3: a Math \[text\] that says "$d eq.not r\_n quad upright("for every ") n$" - more\_rows: a Math \[gray\] that says "$dots$" drawn in sheet - new\_cells: a Math \[red\] that says "$2$" drawn in sheet - new\_cells\_2: a Math \[red\] that says "$4$" drawn in sheet - new\_cells\_3: a Math \[red\] that says "$8$" drawn in sheet - new\_cells\_4: a Math \[red\] that says "$1$" drawn in sheet - new\_label: a Math \[red\] that says "$d$" drawn in sheet - new\_point: a Math \[red\] that says "$0.$" drawn in sheet - new\_tail: a Math \[red\] that says "$dots$" drawn in sheet - plan: a Panel that says "No program computes $H$. Not a slow one, not a clever one, not one with a bigger machine underneath it. None at all." - row\_labels: a Math \[gray\] that says "$r\_1$" drawn in sheet - row\_labels\_2: a Math \[gray\] that says "$r\_2$" drawn in sheet - row\_labels\_3: a Math \[gray\] that says "$r\_3$" drawn in sheet - row\_labels\_4: a Math \[gray\] that says "$r\_4$" drawn in sheet - row\_points: a Math \[text\] that says "$0.$" drawn in sheet - row\_points\_2: a Math \[text\] that says "$0.$" drawn in sheet - row\_points\_3: a Math \[text\] that says "$0.$" drawn in sheet - row\_points\_4: a Math \[text\] that says "$0.$" drawn in sheet - row\_tails: a Math \[gray\] that says "$dots$" drawn in sheet - row\_tails\_2: a Math \[gray\] that says "$dots$" drawn in sheet - row\_tails\_3: a Math \[gray\] that says "$dots$" drawn in sheet - row\_tails\_4: a Math \[gray\] that says "$dots$" drawn in sheet - rule: a Math \[text\] that says "$d\_n = r\_(n n) + 1, quad 9 arrow.r 1$" - sheet: a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)) - steps: a Block \[text\] that says "Assume a complete table, one row per object. Read the entries down the diagonal. Build a new object that disagrees with row $n$ at position $n$. The new object is on no row, so the table was never complete." #### Beats ##### [00:00](https://academa.ai/lectures/halting-problem-undecidability?t=0) Narration: 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. Board: Empty. Actions: - [00:00](https://academa.ai/lectures/halting-problem-undecidability?t=0): card is shown on the screen, written out. - [00:1.5](https://academa.ai/lectures/halting-problem-undecidability?t=1.5): card: enter:write-left-to-right. - [00:17.206](https://academa.ai/lectures/halting-problem-undecidability?t=17.2055): card is hidden from the screen — left the board. ##### [00:18.405](https://academa.ai/lectures/halting-problem-undecidability?t=18.4055) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [00:18.405](https://academa.ai/lectures/halting-problem-undecidability?t=18.4055): head\_plan is shown on the screen, written out. - [00:30.561](https://academa.ai/lectures/halting-problem-undecidability?t=30.561): decider is shown on the screen, written out. ##### [00:32.09](https://academa.ai/lectures/halting-problem-undecidability?t=32.09) Narration: 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. Board: decider — a Math \[text\] that says "$H(P, x) = upright("halts") quad upright("or") quad upright("loops")$"; head\_plan — a Heading that says "The Question We Are Asking" Actions: - [00:41.32](https://academa.ai/lectures/halting-problem-undecidability?t=41.32): decider (the "upright("halts")" part) is emphasized. - [00:42.121](https://academa.ai/lectures/halting-problem-undecidability?t=42.121): decider (the "upright("halts")" part) is no longer emphasized. - [00:42.121](https://academa.ai/lectures/halting-problem-undecidability?t=42.121): decider (the "upright("loops")" part) is emphasized. - [00:45.291](https://academa.ai/lectures/halting-problem-undecidability?t=45.291000000000004): plan is shown on the screen, written out. - [00:47.485](https://academa.ai/lectures/halting-problem-undecidability?t=47.48500000000001): decider (the "upright("loops")" part) is no longer emphasized. ##### [00:49.061](https://academa.ai/lectures/halting-problem-undecidability?t=49.060500000000005) Narration: 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. Board: decider — a Math \[text\] that says "$H(P, x) = upright("halts") quad upright("or") quad upright("loops")$"; plan — a Panel that says "No program computes $H$. Not a slow one, not a clever one, not one with a bigger machine underneath it. None at all."; head\_plan — a Heading that says "The Question We Are Asking" Actions: - [00:50.291](https://academa.ai/lectures/halting-problem-undecidability?t=50.291000000000004): plan (the "None at all" part) is emphasized. - [00:58.859](https://academa.ai/lectures/halting-problem-undecidability?t=58.859): plan (the "None at all" part) is no longer emphasized. - [00:59.777](https://academa.ai/lectures/halting-problem-undecidability?t=59.776500000000006): decider is hidden from the screen — left the board. - [00:59.777](https://academa.ai/lectures/halting-problem-undecidability?t=59.776500000000006): head\_plan is hidden from the screen — left the board. - [00:59.777](https://academa.ai/lectures/halting-problem-undecidability?t=59.776500000000006): plan is hidden from the screen — left the board. ##### [01:0.977](https://academa.ai/lectures/halting-problem-undecidability?t=60.9765) Narration: 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. Board: Empty. Actions: - [01:0.977](https://academa.ai/lectures/halting-problem-undecidability?t=60.9765): head\_list is shown on the screen, written out. - [01:0.977](https://academa.ai/lectures/halting-problem-undecidability?t=60.9765): sheet is shown on the screen, written out. - [01:4.796](https://academa.ai/lectures/halting-problem-undecidability?t=64.79599999999999): row\_labels is shown on the screen, written out. - [01:4.796](https://academa.ai/lectures/halting-problem-undecidability?t=64.79599999999999): row\_points is shown on the screen, written out. - [01:4.796](https://academa.ai/lectures/halting-problem-undecidability?t=64.79599999999999): cells is shown on the screen, written out. - [01:4.796](https://academa.ai/lectures/halting-problem-undecidability?t=64.79599999999999): cells\_2 is shown on the screen, written out. - [01:4.796](https://academa.ai/lectures/halting-problem-undecidability?t=64.79599999999999): cells\_3 is shown on the screen, written out. - [01:4.796](https://academa.ai/lectures/halting-problem-undecidability?t=64.79599999999999): cells\_4 is shown on the screen, written out. - [01:4.796](https://academa.ai/lectures/halting-problem-undecidability?t=64.79599999999999): cells\_5 is shown on the screen, written out. - [01:4.796](https://academa.ai/lectures/halting-problem-undecidability?t=64.79599999999999): row\_tails is shown on the screen, written out. - [01:5.146](https://academa.ai/lectures/halting-problem-undecidability?t=65.14599999999999): row\_labels\_2 is shown on the screen, written out. - [01:5.146](https://academa.ai/lectures/halting-problem-undecidability?t=65.14599999999999): row\_points\_2 is shown on the screen, written out. - [01:5.146](https://academa.ai/lectures/halting-problem-undecidability?t=65.14599999999999): cells\_6 is shown on the screen, written out. - [01:5.146](https://academa.ai/lectures/halting-problem-undecidability?t=65.14599999999999): cells\_7 is shown on the screen, written out. - [01:5.146](https://academa.ai/lectures/halting-problem-undecidability?t=65.14599999999999): cells\_8 is shown on the screen, written out. - [01:5.146](https://academa.ai/lectures/halting-problem-undecidability?t=65.14599999999999): cells\_9 is shown on the screen, written out. - [01:5.146](https://academa.ai/lectures/halting-problem-undecidability?t=65.14599999999999): cells\_10 is shown on the screen, written out. - [01:5.146](https://academa.ai/lectures/halting-problem-undecidability?t=65.14599999999999): row\_tails\_2 is shown on the screen, written out. - [01:5.496](https://academa.ai/lectures/halting-problem-undecidability?t=65.49599999999998): row\_labels\_3 is shown on the screen, written out. - [01:5.496](https://academa.ai/lectures/halting-problem-undecidability?t=65.49599999999998): row\_points\_3 is shown on the screen, written out. - [01:5.496](https://academa.ai/lectures/halting-problem-undecidability?t=65.49599999999998): cells\_11 is shown on the screen, written out. - [01:5.496](https://academa.ai/lectures/halting-problem-undecidability?t=65.49599999999998): cells\_12 is shown on the screen, written out. - [01:5.496](https://academa.ai/lectures/halting-problem-undecidability?t=65.49599999999998): cells\_13 is shown on the screen, written out. - [01:5.496](https://academa.ai/lectures/halting-problem-undecidability?t=65.49599999999998): cells\_14 is shown on the screen, written out. - [01:5.496](https://academa.ai/lectures/halting-problem-undecidability?t=65.49599999999998): cells\_15 is shown on the screen, written out. - [01:5.496](https://academa.ai/lectures/halting-problem-undecidability?t=65.49599999999998): row\_tails\_3 is shown on the screen, written out. - [01:5.846](https://academa.ai/lectures/halting-problem-undecidability?t=65.84599999999998): row\_labels\_4 is shown on the screen, written out. - [01:5.846](https://academa.ai/lectures/halting-problem-undecidability?t=65.84599999999998): row\_points\_4 is shown on the screen, written out. - [01:5.846](https://academa.ai/lectures/halting-problem-undecidability?t=65.84599999999998): cells\_16 is shown on the screen, written out. - [01:5.846](https://academa.ai/lectures/halting-problem-undecidability?t=65.84599999999998): cells\_17 is shown on the screen, written out. - [01:5.846](https://academa.ai/lectures/halting-problem-undecidability?t=65.84599999999998): cells\_18 is shown on the screen, written out. - [01:5.846](https://academa.ai/lectures/halting-problem-undecidability?t=65.84599999999998): cells\_19 is shown on the screen, written out. - [01:5.846](https://academa.ai/lectures/halting-problem-undecidability?t=65.84599999999998): cells\_20 is shown on the screen, written out. - [01:5.846](https://academa.ai/lectures/halting-problem-undecidability?t=65.84599999999998): row\_tails\_4 is shown on the screen, written out. - [01:6.196](https://academa.ai/lectures/halting-problem-undecidability?t=66.19599999999997): more\_rows is shown on the screen, written out. - [01:14.05](https://academa.ai/lectures/halting-problem-undecidability?t=74.05000000000001): sheet moves to a new place on the board. - [01:14.05](https://academa.ai/lectures/halting-problem-undecidability?t=74.05000000000001): claim is shown on the screen, written out. ##### [01:15.602](https://academa.ai/lectures/halting-problem-undecidability?t=75.6015) Narration: 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. Board: claim — a Text \[text\] that says "Every real number between 0 and 1 is somewhere on this list."; sheet — a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)); head\_list — a Heading that says "Suppose the List Is Complete"; row\_labels — a Math \[gray\] that says "$r\_1$" drawn in sheet; row\_points — a Math \[text\] that says "$0.$" drawn in sheet; cells — a Math \[text\] that says "$1$" drawn in sheet; cells\_2 — a Math \[text\] that says "$4$" drawn in sheet; cells\_3 — a Math \[text\] that says "$1$" drawn in sheet; cells\_4 — a Math \[text\] that says "$5$" drawn in sheet; cells\_5 — a Math \[text\] that says "$9$" drawn in sheet; row\_tails — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_2 — a Math \[gray\] that says "$r\_2$" drawn in sheet; row\_points\_2 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_6 — a Math \[text\] that says "$3$" drawn in sheet; cells\_7 — a Math \[text\] that says "$3$" drawn in sheet; cells\_8 — a Math \[text\] that says "$3$" drawn in sheet; cells\_9 — a Math \[text\] that says "$3$" drawn in sheet; cells\_10 — a Math \[text\] that says "$3$" drawn in sheet; row\_tails\_2 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_3 — a Math \[gray\] that says "$r\_3$" drawn in sheet; row\_points\_3 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_11 — a Math \[text\] that says "$7$" drawn in sheet; cells\_12 — a Math \[text\] that says "$0$" drawn in sheet; cells\_13 — a Math \[text\] that says "$7$" drawn in sheet; cells\_14 — a Math \[text\] that says "$1$" drawn in sheet; cells\_15 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_3 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_4 — a Math \[gray\] that says "$r\_4$" drawn in sheet; row\_points\_4 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_16 — a Math \[text\] that says "$5$" drawn in sheet; cells\_17 — a Math \[text\] that says "$0$" drawn in sheet; cells\_18 — a Math \[text\] that says "$0$" drawn in sheet; cells\_19 — a Math \[text\] that says "$0$" drawn in sheet; cells\_20 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_4 — a Math \[gray\] that says "$dots$" drawn in sheet; more\_rows — a Math \[gray\] that says "$dots$" drawn in sheet Actions: - [01:22.567](https://academa.ai/lectures/halting-problem-undecidability?t=82.56700000000001): cells is indicated — a transient flash. - [01:26.793](https://academa.ai/lectures/halting-problem-undecidability?t=86.793): cells\_7 is indicated — a transient flash. ##### [01:30.865](https://academa.ai/lectures/halting-problem-undecidability?t=90.8645) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [01:31.399](https://academa.ai/lectures/halting-problem-undecidability?t=91.39900000000002): cells\_13 is indicated — a transient flash. - [01:34.22](https://academa.ai/lectures/halting-problem-undecidability?t=94.22000000000003): cells\_19 is indicated — a transient flash. - [01:38.713](https://academa.ai/lectures/halting-problem-undecidability?t=98.71300000000002): guide is shown on the screen, drawn. ##### [01:43.725](https://academa.ai/lectures/halting-problem-undecidability?t=103.72500000000001) Narration: 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. Board: claim — a Text \[text\] that says "Every real number between 0 and 1 is somewhere on this list."; sheet — a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)); head\_list — a Heading that says "Suppose the List Is Complete"; row\_labels — a Math \[gray\] that says "$r\_1$" drawn in sheet; row\_points — a Math \[text\] that says "$0.$" drawn in sheet; cells — a Math \[text\] that says "$1$" drawn in sheet; cells\_2 — a Math \[text\] that says "$4$" drawn in sheet; cells\_3 — a Math \[text\] that says "$1$" drawn in sheet; cells\_4 — a Math \[text\] that says "$5$" drawn in sheet; cells\_5 — a Math \[text\] that says "$9$" drawn in sheet; row\_tails — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_2 — a Math \[gray\] that says "$r\_2$" drawn in sheet; row\_points\_2 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_6 — a Math \[text\] that says "$3$" drawn in sheet; cells\_7 — a Math \[text\] that says "$3$" drawn in sheet; cells\_8 — a Math \[text\] that says "$3$" drawn in sheet; cells\_9 — a Math \[text\] that says "$3$" drawn in sheet; cells\_10 — a Math \[text\] that says "$3$" drawn in sheet; row\_tails\_2 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_3 — a Math \[gray\] that says "$r\_3$" drawn in sheet; row\_points\_3 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_11 — a Math \[text\] that says "$7$" drawn in sheet; cells\_12 — a Math \[text\] that says "$0$" drawn in sheet; cells\_13 — a Math \[text\] that says "$7$" drawn in sheet; cells\_14 — a Math \[text\] that says "$1$" drawn in sheet; cells\_15 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_3 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_4 — a Math \[gray\] that says "$r\_4$" drawn in sheet; row\_points\_4 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_16 — a Math \[text\] that says "$5$" drawn in sheet; cells\_17 — a Math \[text\] that says "$0$" drawn in sheet; cells\_18 — a Math \[text\] that says "$0$" drawn in sheet; cells\_19 — a Math \[text\] that says "$0$" drawn in sheet; cells\_20 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_4 — a Math \[gray\] that says "$dots$" drawn in sheet; more\_rows — a Math \[gray\] that says "$dots$" drawn in sheet; guide — a Line \[yellow\] drawn in sheet (start=(2.55, 5.85), end=(5.95, 2.45), dashed=True) Actions: - [01:44.398](https://academa.ai/lectures/halting-problem-undecidability?t=104.39800000000001): rule is shown on the screen, written out. - [01:44.944](https://academa.ai/lectures/halting-problem-undecidability?t=104.94400000000002): divider is shown on the screen, written out. - [01:44.944](https://academa.ai/lectures/halting-problem-undecidability?t=104.94400000000002): new\_label is shown on the screen, written out. - [01:44.944](https://academa.ai/lectures/halting-problem-undecidability?t=104.94400000000002): new\_point is shown on the screen, written out. ##### [01:58.024](https://academa.ai/lectures/halting-problem-undecidability?t=118.024) Narration: One becomes two. Three becomes four. Seven becomes eight. And zero becomes one. Call the result d. Board: claim — a Text \[text\] that says "Every real number between 0 and 1 is somewhere on this list."; rule — a Math \[text\] that says "$d\_n = r\_(n n) + 1, quad 9 arrow.r 1$"; sheet — a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)); head\_list — a Heading that says "Suppose the List Is Complete"; row\_labels — a Math \[gray\] that says "$r\_1$" drawn in sheet; row\_points — a Math \[text\] that says "$0.$" drawn in sheet; cells — a Math \[text\] that says "$1$" drawn in sheet; cells\_2 — a Math \[text\] that says "$4$" drawn in sheet; cells\_3 — a Math \[text\] that says "$1$" drawn in sheet; cells\_4 — a Math \[text\] that says "$5$" drawn in sheet; cells\_5 — a Math \[text\] that says "$9$" drawn in sheet; row\_tails — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_2 — a Math \[gray\] that says "$r\_2$" drawn in sheet; row\_points\_2 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_6 — a Math \[text\] that says "$3$" drawn in sheet; cells\_7 — a Math \[text\] that says "$3$" drawn in sheet; cells\_8 — a Math \[text\] that says "$3$" drawn in sheet; cells\_9 — a Math \[text\] that says "$3$" drawn in sheet; cells\_10 — a Math \[text\] that says "$3$" drawn in sheet; row\_tails\_2 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_3 — a Math \[gray\] that says "$r\_3$" drawn in sheet; row\_points\_3 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_11 — a Math \[text\] that says "$7$" drawn in sheet; cells\_12 — a Math \[text\] that says "$0$" drawn in sheet; cells\_13 — a Math \[text\] that says "$7$" drawn in sheet; cells\_14 — a Math \[text\] that says "$1$" drawn in sheet; cells\_15 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_3 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_4 — a Math \[gray\] that says "$r\_4$" drawn in sheet; row\_points\_4 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_16 — a Math \[text\] that says "$5$" drawn in sheet; cells\_17 — a Math \[text\] that says "$0$" drawn in sheet; cells\_18 — a Math \[text\] that says "$0$" drawn in sheet; cells\_19 — a Math \[text\] that says "$0$" drawn in sheet; cells\_20 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_4 — a Math \[gray\] that says "$dots$" drawn in sheet; more\_rows — a Math \[gray\] that says "$dots$" drawn in sheet; guide — a Line \[yellow\] drawn in sheet (start=(2.55, 5.85), end=(5.95, 2.45), dashed=True); divider — a Line \[gray\] drawn in sheet (start=(0.7, 1.55), end=(7.8, 1.55), dashed=True); new\_label — a Math \[red\] that says "$d$" drawn in sheet; new\_point — a Math \[red\] that says "$0.$" drawn in sheet Actions: - [01:58.976](https://academa.ai/lectures/halting-problem-undecidability?t=118.97600000000001): new\_cells is shown on the screen, written out. - [02:0.88](https://academa.ai/lectures/halting-problem-undecidability?t=120.88000000000001): new\_cells\_2 is shown on the screen, written out. - [02:2.784](https://academa.ai/lectures/halting-problem-undecidability?t=122.784): new\_cells\_3 is shown on the screen, written out. - [02:4.096](https://academa.ai/lectures/halting-problem-undecidability?t=124.096): new\_cells\_4 is shown on the screen, written out. ##### [02:8.121](https://academa.ai/lectures/halting-problem-undecidability?t=128.121) Narration: 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? Board: claim — a Text \[text\] that says "Every real number between 0 and 1 is somewhere on this list."; rule — a Math \[text\] that says "$d\_n = r\_(n n) + 1, quad 9 arrow.r 1$"; sheet — a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)); head\_list — a Heading that says "Suppose the List Is Complete"; row\_labels — a Math \[gray\] that says "$r\_1$" drawn in sheet; row\_points — a Math \[text\] that says "$0.$" drawn in sheet; cells — a Math \[text\] that says "$1$" drawn in sheet; cells\_2 — a Math \[text\] that says "$4$" drawn in sheet; cells\_3 — a Math \[text\] that says "$1$" drawn in sheet; cells\_4 — a Math \[text\] that says "$5$" drawn in sheet; cells\_5 — a Math \[text\] that says "$9$" drawn in sheet; row\_tails — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_2 — a Math \[gray\] that says "$r\_2$" drawn in sheet; row\_points\_2 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_6 — a Math \[text\] that says "$3$" drawn in sheet; cells\_7 — a Math \[text\] that says "$3$" drawn in sheet; cells\_8 — a Math \[text\] that says "$3$" drawn in sheet; cells\_9 — a Math \[text\] that says "$3$" drawn in sheet; cells\_10 — a Math \[text\] that says "$3$" drawn in sheet; row\_tails\_2 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_3 — a Math \[gray\] that says "$r\_3$" drawn in sheet; row\_points\_3 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_11 — a Math \[text\] that says "$7$" drawn in sheet; cells\_12 — a Math \[text\] that says "$0$" drawn in sheet; cells\_13 — a Math \[text\] that says "$7$" drawn in sheet; cells\_14 — a Math \[text\] that says "$1$" drawn in sheet; cells\_15 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_3 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_4 — a Math \[gray\] that says "$r\_4$" drawn in sheet; row\_points\_4 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_16 — a Math \[text\] that says "$5$" drawn in sheet; cells\_17 — a Math \[text\] that says "$0$" drawn in sheet; cells\_18 — a Math \[text\] that says "$0$" drawn in sheet; cells\_19 — a Math \[text\] that says "$0$" drawn in sheet; cells\_20 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_4 — a Math \[gray\] that says "$dots$" drawn in sheet; more\_rows — a Math \[gray\] that says "$dots$" drawn in sheet; guide — a Line \[yellow\] drawn in sheet (start=(2.55, 5.85), end=(5.95, 2.45), dashed=True); divider — a Line \[gray\] drawn in sheet (start=(0.7, 1.55), end=(7.8, 1.55), dashed=True); new\_label — a Math \[red\] that says "$d$" drawn in sheet; new\_point — a Math \[red\] that says "$0.$" drawn in sheet; new\_cells — a Math \[red\] that says "$2$" drawn in sheet; new\_cells\_2 — a Math \[red\] that says "$4$" drawn in sheet; new\_cells\_3 — a Math \[red\] that says "$8$" drawn in sheet; new\_cells\_4 — a Math \[red\] that says "$1$" drawn in sheet Actions: - [02:12.486](https://academa.ai/lectures/halting-problem-undecidability?t=132.48600000000002): new\_tail is shown on the screen, written out. - [02:20.474](https://academa.ai/lectures/halting-problem-undecidability?t=140.4735): rule moves to a new place on the board. - [02:20.474](https://academa.ai/lectures/halting-problem-undecidability?t=140.4735): claim is hidden from the screen — left the board. - [02:20.474](https://academa.ai/lectures/halting-problem-undecidability?t=140.4735): head\_list is hidden from the screen — left the board. ##### [02:21.073](https://academa.ai/lectures/halting-problem-undecidability?t=141.0735) Narration: It cannot be the first number, because d was built to differ from the first number in the first decimal place. Two, not one. Board: rule — a Math \[text\] that says "$d\_n = r\_(n n) + 1, quad 9 arrow.r 1$"; sheet — a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)); row\_labels — a Math \[gray\] that says "$r\_1$" drawn in sheet; row\_points — a Math \[text\] that says "$0.$" drawn in sheet; cells — a Math \[text\] that says "$1$" drawn in sheet; cells\_2 — a Math \[text\] that says "$4$" drawn in sheet; cells\_3 — a Math \[text\] that says "$1$" drawn in sheet; cells\_4 — a Math \[text\] that says "$5$" drawn in sheet; cells\_5 — a Math \[text\] that says "$9$" drawn in sheet; row\_tails — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_2 — a Math \[gray\] that says "$r\_2$" drawn in sheet; row\_points\_2 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_6 — a Math \[text\] that says "$3$" drawn in sheet; cells\_7 — a Math \[text\] that says "$3$" drawn in sheet; cells\_8 — a Math \[text\] that says "$3$" drawn in sheet; cells\_9 — a Math \[text\] that says "$3$" drawn in sheet; cells\_10 — a Math \[text\] that says "$3$" drawn in sheet; row\_tails\_2 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_3 — a Math \[gray\] that says "$r\_3$" drawn in sheet; row\_points\_3 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_11 — a Math \[text\] that says "$7$" drawn in sheet; cells\_12 — a Math \[text\] that says "$0$" drawn in sheet; cells\_13 — a Math \[text\] that says "$7$" drawn in sheet; cells\_14 — a Math \[text\] that says "$1$" drawn in sheet; cells\_15 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_3 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_4 — a Math \[gray\] that says "$r\_4$" drawn in sheet; row\_points\_4 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_16 — a Math \[text\] that says "$5$" drawn in sheet; cells\_17 — a Math \[text\] that says "$0$" drawn in sheet; cells\_18 — a Math \[text\] that says "$0$" drawn in sheet; cells\_19 — a Math \[text\] that says "$0$" drawn in sheet; cells\_20 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_4 — a Math \[gray\] that says "$dots$" drawn in sheet; more\_rows — a Math \[gray\] that says "$dots$" drawn in sheet; guide — a Line \[yellow\] drawn in sheet (start=(2.55, 5.85), end=(5.95, 2.45), dashed=True); divider — a Line \[gray\] drawn in sheet (start=(0.7, 1.55), end=(7.8, 1.55), dashed=True); new\_label — a Math \[red\] that says "$d$" drawn in sheet; new\_point — a Math \[red\] that says "$0.$" drawn in sheet; new\_cells — a Math \[red\] that says "$2$" drawn in sheet; new\_cells\_2 — a Math \[red\] that says "$4$" drawn in sheet; new\_cells\_3 — a Math \[red\] that says "$8$" drawn in sheet; new\_cells\_4 — a Math \[red\] that says "$1$" drawn in sheet; new\_tail — a Math \[red\] that says "$dots$" drawn in sheet Actions: - [02:21.073](https://academa.ai/lectures/halting-problem-undecidability?t=141.0735): head\_check is shown on the screen, written out. - [02:21.666](https://academa.ai/lectures/halting-problem-undecidability?t=141.666): m1 is shown on the screen, written out. - [02:27.691](https://academa.ai/lectures/halting-problem-undecidability?t=147.69099999999997): new\_cells is indicated — a transient flash. - [02:28.585](https://academa.ai/lectures/halting-problem-undecidability?t=148.58499999999998): cells is indicated — a transient flash. ##### [02:29.986](https://academa.ai/lectures/halting-problem-undecidability?t=149.986) Narration: 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. Board: rule — a Math \[text\] that says "$d\_n = r\_(n n) + 1, quad 9 arrow.r 1$"; sheet — a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)); row\_labels — a Math \[gray\] that says "$r\_1$" drawn in sheet; row\_points — a Math \[text\] that says "$0.$" drawn in sheet; cells — a Math \[text\] that says "$1$" drawn in sheet; cells\_2 — a Math \[text\] that says "$4$" drawn in sheet; cells\_3 — a Math \[text\] that says "$1$" drawn in sheet; cells\_4 — a Math \[text\] that says "$5$" drawn in sheet; cells\_5 — a Math \[text\] that says "$9$" drawn in sheet; row\_tails — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_2 — a Math \[gray\] that says "$r\_2$" drawn in sheet; row\_points\_2 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_6 — a Math \[text\] that says "$3$" drawn in sheet; cells\_7 — a Math \[text\] that says "$3$" drawn in sheet; cells\_8 — a Math \[text\] that says "$3$" drawn in sheet; cells\_9 — a Math \[text\] that says "$3$" drawn in sheet; cells\_10 — a Math \[text\] that says "$3$" drawn in sheet; row\_tails\_2 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_3 — a Math \[gray\] that says "$r\_3$" drawn in sheet; row\_points\_3 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_11 — a Math \[text\] that says "$7$" drawn in sheet; cells\_12 — a Math \[text\] that says "$0$" drawn in sheet; cells\_13 — a Math \[text\] that says "$7$" drawn in sheet; cells\_14 — a Math \[text\] that says "$1$" drawn in sheet; cells\_15 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_3 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_4 — a Math \[gray\] that says "$r\_4$" drawn in sheet; row\_points\_4 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_16 — a Math \[text\] that says "$5$" drawn in sheet; cells\_17 — a Math \[text\] that says "$0$" drawn in sheet; cells\_18 — a Math \[text\] that says "$0$" drawn in sheet; cells\_19 — a Math \[text\] that says "$0$" drawn in sheet; cells\_20 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_4 — a Math \[gray\] that says "$dots$" drawn in sheet; more\_rows — a Math \[gray\] that says "$dots$" drawn in sheet; guide — a Line \[yellow\] drawn in sheet (start=(2.55, 5.85), end=(5.95, 2.45), dashed=True); divider — a Line \[gray\] drawn in sheet (start=(0.7, 1.55), end=(7.8, 1.55), dashed=True); new\_label — a Math \[red\] that says "$d$" drawn in sheet; new\_point — a Math \[red\] that says "$0.$" drawn in sheet; new\_cells — a Math \[red\] that says "$2$" drawn in sheet; new\_cells\_2 — a Math \[red\] that says "$4$" drawn in sheet; new\_cells\_3 — a Math \[red\] that says "$8$" drawn in sheet; new\_cells\_4 — a Math \[red\] that says "$1$" drawn in sheet; new\_tail — a Math \[red\] that says "$dots$" drawn in sheet; m1 — a Math \[text\] that says "$d eq.not r\_1$"; head\_check — a Heading that says "Is the New Number on the List?" Actions: - [02:31.182](https://academa.ai/lectures/halting-problem-undecidability?t=151.182): m2 is shown on the screen, written out. - [02:34.177](https://academa.ai/lectures/halting-problem-undecidability?t=154.17699999999996): new\_cells\_2 is indicated — a transient flash. - [02:35.013](https://academa.ai/lectures/halting-problem-undecidability?t=155.01299999999998): cells\_7 is indicated — a transient flash. ##### [02:40.756](https://academa.ai/lectures/halting-problem-undecidability?t=160.7565) Narration: 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. Board: rule — a Math \[text\] that says "$d\_n = r\_(n n) + 1, quad 9 arrow.r 1$"; sheet — a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)); row\_labels — a Math \[gray\] that says "$r\_1$" drawn in sheet; row\_points — a Math \[text\] that says "$0.$" drawn in sheet; cells — a Math \[text\] that says "$1$" drawn in sheet; cells\_2 — a Math \[text\] that says "$4$" drawn in sheet; cells\_3 — a Math \[text\] that says "$1$" drawn in sheet; cells\_4 — a Math \[text\] that says "$5$" drawn in sheet; cells\_5 — a Math \[text\] that says "$9$" drawn in sheet; row\_tails — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_2 — a Math \[gray\] that says "$r\_2$" drawn in sheet; row\_points\_2 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_6 — a Math \[text\] that says "$3$" drawn in sheet; cells\_7 — a Math \[text\] that says "$3$" drawn in sheet; cells\_8 — a Math \[text\] that says "$3$" drawn in sheet; cells\_9 — a Math \[text\] that says "$3$" drawn in sheet; cells\_10 — a Math \[text\] that says "$3$" drawn in sheet; row\_tails\_2 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_3 — a Math \[gray\] that says "$r\_3$" drawn in sheet; row\_points\_3 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_11 — a Math \[text\] that says "$7$" drawn in sheet; cells\_12 — a Math \[text\] that says "$0$" drawn in sheet; cells\_13 — a Math \[text\] that says "$7$" drawn in sheet; cells\_14 — a Math \[text\] that says "$1$" drawn in sheet; cells\_15 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_3 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_4 — a Math \[gray\] that says "$r\_4$" drawn in sheet; row\_points\_4 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_16 — a Math \[text\] that says "$5$" drawn in sheet; cells\_17 — a Math \[text\] that says "$0$" drawn in sheet; cells\_18 — a Math \[text\] that says "$0$" drawn in sheet; cells\_19 — a Math \[text\] that says "$0$" drawn in sheet; cells\_20 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_4 — a Math \[gray\] that says "$dots$" drawn in sheet; more\_rows — a Math \[gray\] that says "$dots$" drawn in sheet; guide — a Line \[yellow\] drawn in sheet (start=(2.55, 5.85), end=(5.95, 2.45), dashed=True); divider — a Line \[gray\] drawn in sheet (start=(0.7, 1.55), end=(7.8, 1.55), dashed=True); new\_label — a Math \[red\] that says "$d$" drawn in sheet; new\_point — a Math \[red\] that says "$0.$" drawn in sheet; new\_cells — a Math \[red\] that says "$2$" drawn in sheet; new\_cells\_2 — a Math \[red\] that says "$4$" drawn in sheet; new\_cells\_3 — a Math \[red\] that says "$8$" drawn in sheet; new\_cells\_4 — a Math \[red\] that says "$1$" drawn in sheet; new\_tail — a Math \[red\] that says "$dots$" drawn in sheet; m1 — a Math \[text\] that says "$d eq.not r\_1$"; m2 — a Math \[text\] that says "$d eq.not r\_2$"; head\_check — a Heading that says "Is the New Number on the List?" Actions: - [02:41.755](https://academa.ai/lectures/halting-problem-undecidability?t=161.75499999999997): m3 is shown on the screen, written out. - [02:47.269](https://academa.ai/lectures/halting-problem-undecidability?t=167.26899999999998): rule is indicated — a transient flash. ##### [02:58.481](https://academa.ai/lectures/halting-problem-undecidability?t=178.48149999999998) Narration: 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. Board: rule — a Math \[text\] that says "$d\_n = r\_(n n) + 1, quad 9 arrow.r 1$"; sheet — a Figure (x\_range=(0.4, 8.2), y\_range=(0.4, 6.2), aspect=(7.8, 5.8)); row\_labels — a Math \[gray\] that says "$r\_1$" drawn in sheet; row\_points — a Math \[text\] that says "$0.$" drawn in sheet; cells — a Math \[text\] that says "$1$" drawn in sheet; cells\_2 — a Math \[text\] that says "$4$" drawn in sheet; cells\_3 — a Math \[text\] that says "$1$" drawn in sheet; cells\_4 — a Math \[text\] that says "$5$" drawn in sheet; cells\_5 — a Math \[text\] that says "$9$" drawn in sheet; row\_tails — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_2 — a Math \[gray\] that says "$r\_2$" drawn in sheet; row\_points\_2 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_6 — a Math \[text\] that says "$3$" drawn in sheet; cells\_7 — a Math \[text\] that says "$3$" drawn in sheet; cells\_8 — a Math \[text\] that says "$3$" drawn in sheet; cells\_9 — a Math \[text\] that says "$3$" drawn in sheet; cells\_10 — a Math \[text\] that says "$3$" drawn in sheet; row\_tails\_2 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_3 — a Math \[gray\] that says "$r\_3$" drawn in sheet; row\_points\_3 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_11 — a Math \[text\] that says "$7$" drawn in sheet; cells\_12 — a Math \[text\] that says "$0$" drawn in sheet; cells\_13 — a Math \[text\] that says "$7$" drawn in sheet; cells\_14 — a Math \[text\] that says "$1$" drawn in sheet; cells\_15 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_3 — a Math \[gray\] that says "$dots$" drawn in sheet; row\_labels\_4 — a Math \[gray\] that says "$r\_4$" drawn in sheet; row\_points\_4 — a Math \[text\] that says "$0.$" drawn in sheet; cells\_16 — a Math \[text\] that says "$5$" drawn in sheet; cells\_17 — a Math \[text\] that says "$0$" drawn in sheet; cells\_18 — a Math \[text\] that says "$0$" drawn in sheet; cells\_19 — a Math \[text\] that says "$0$" drawn in sheet; cells\_20 — a Math \[text\] that says "$0$" drawn in sheet; row\_tails\_4 — a Math \[gray\] that says "$dots$" drawn in sheet; more\_rows — a Math \[gray\] that says "$dots$" drawn in sheet; guide — a Line \[yellow\] drawn in sheet (start=(2.55, 5.85), end=(5.95, 2.45), dashed=True); divider — a Line \[gray\] drawn in sheet (start=(0.7, 1.55), end=(7.8, 1.55), dashed=True); new\_label — a Math \[red\] that says "$d$" drawn in sheet; new\_point — a Math \[red\] that says "$0.$" drawn in sheet; new\_cells — a Math \[red\] that says "$2$" drawn in sheet; new\_cells\_2 — a Math \[red\] that says "$4$" drawn in sheet; new\_cells\_3 — a Math \[red\] that says "$8$" drawn in sheet; new\_cells\_4 — a Math \[red\] that says "$1$" drawn in sheet; new\_tail — a Math \[red\] that says "$dots$" drawn in sheet; m1 — a Math \[text\] that says "$d eq.not r\_1$"; m2 — a Math \[text\] that says "$d eq.not r\_2$"; m3 — a Math \[text\] that says "$d eq.not r\_n quad upright("for every ") n$"; head\_check — a Heading that says "Is the New Number on the List?" Actions: - [02:59.352](https://academa.ai/lectures/halting-problem-undecidability?t=179.35199999999995): A box is drawn around m3. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): head\_check is hidden from the screen — left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): m1 is hidden from the screen — left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): m2 is hidden from the screen — left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): m3 is hidden from the screen — left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): rule is hidden from the screen — left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): sheet is hidden from the screen — left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_labels is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_points is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_2 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_3 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_4 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_5 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_tails is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_labels\_2 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_points\_2 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_6 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_7 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_8 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_9 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_10 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_tails\_2 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_labels\_3 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_points\_3 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_11 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_12 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_13 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_14 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_15 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_tails\_3 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_labels\_4 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_points\_4 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_16 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_17 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_18 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_19 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): cells\_20 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): row\_tails\_4 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): more\_rows is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): guide is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): divider is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): new\_label is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): new\_point is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): new\_cells is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): new\_cells\_2 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): new\_cells\_3 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): new\_cells\_4 is hidden from the screen — sheet left the board. - [03:8.628](https://academa.ai/lectures/halting-problem-undecidability?t=188.62849999999997): new\_tail is hidden from the screen — sheet left the board. ##### [03:9.828](https://academa.ai/lectures/halting-problem-undecidability?t=189.8285) Narration: 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. Board: Empty. Actions: - [03:9.828](https://academa.ai/lectures/halting-problem-undecidability?t=189.8285): head\_shape is shown on the screen, written out. - [03:11.454](https://academa.ai/lectures/halting-problem-undecidability?t=191.45399999999998): steps is shown on the screen, written out. - [03:16.643](https://academa.ai/lectures/halting-problem-undecidability?t=196.64299999999997): steps (the "Assume" part) is emphasized. - [03:21.786](https://academa.ai/lectures/halting-problem-undecidability?t=201.78599999999997): steps (the "Assume" part) is no longer emphasized. - [03:21.786](https://academa.ai/lectures/halting-problem-undecidability?t=201.78599999999997): steps (the "Read" part) is emphasized. ##### [03:25.149](https://academa.ai/lectures/halting-problem-undecidability?t=205.1495) Narration: 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. Board: steps — a Block \[text\] that says "Assume a complete table, one row per object. Read the entries down the diagonal. Build a new object that disagrees with row $n$ at position $n$. The new object is on no row, so the table was never complete."; head\_shape — a Heading that says "The Shape of the Argument" Actions: - [03:25.834](https://academa.ai/lectures/halting-problem-undecidability?t=205.83399999999997): steps (the "Build" part) is emphasized. - [03:25.834](https://academa.ai/lectures/halting-problem-undecidability?t=205.83399999999997): steps (the "Read" part) is no longer emphasized. - [03:33.194](https://academa.ai/lectures/halting-problem-undecidability?t=213.19399999999996): steps (the "Build" part) is no longer emphasized. - [03:33.194](https://academa.ai/lectures/halting-problem-undecidability?t=213.19399999999996): steps (the "The new object" part) is emphasized. ##### [03:39.297](https://academa.ai/lectures/halting-problem-undecidability?t=219.29749999999999) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [03:39.82](https://academa.ai/lectures/halting-problem-undecidability?t=219.81999999999996): steps (the "The new object" part) is no longer emphasized. - [03:39.82](https://academa.ai/lectures/halting-problem-undecidability?t=219.81999999999996): steps (the "diagonal" part) is emphasized. - [03:49.178](https://academa.ai/lectures/halting-problem-undecidability?t=229.17799999999994): steps (the "diagonal" part) is no longer emphasized. - [03:50.243](https://academa.ai/lectures/halting-problem-undecidability?t=230.2426458333333): head\_shape is hidden from the screen — left the board. - [03:50.243](https://academa.ai/lectures/halting-problem-undecidability?t=230.2426458333333): steps is hidden from the screen — left the board. ### Scene 2: [The Table of Programs](https://academa.ai/lectures/halting-problem-undecidability?t=231.28431249999997) Span: 03:51.284–10:27.343 (231.28431249999997s–627.3433333333335s). #### Objects - bit\_def: a Math \[text\] that says "$1 = upright("halts"), quad 0 = upright("loops")$" - c1: a Math \[text\] that says "$c(k, k) = 1 quad arrow.r quad D upright(" loops")$" - c2: a Math \[text\] that says "$c(k, k) = 0 quad arrow.r quad D upright(" halts")$" - cell\_def: a Math \[text\] that says "$c(i, j) = P\_i upright(" on ") P\_j$" - clash: a Math \[red\] that says "$?$" drawn in table - col\_dots: a Math \[gray\] that says "$dots$" drawn in table - col\_heads: a Math \[gray\] that says "$P\_1$" drawn in table - col\_heads\_2: a Math \[gray\] that says "$P\_2$" drawn in table - col\_heads\_3: a Math \[gray\] that says "$P\_3$" drawn in table - col\_heads\_4: a Math \[gray\] that says "$P\_4$" drawn in table - col\_k: a Math \[red\] that says "$P\_k$" drawn in table - d0: a Math \[text\] that says "$D(P): quad upright("ask ") H(P, P)$" - d1: a Math \[text\] that says "$upright("halts") arrow.r D upright(" loops")$" - d2: a Math \[text\] that says "$upright("loops") arrow.r D upright(" halts")$" - d\_cells: a Math \[red\] that says "$0$" drawn in table - d\_cells\_2: a Math \[red\] that says "$0$" drawn in table - d\_cells\_3: a Math \[red\] that says "$0$" drawn in table - d\_cells\_4: a Math \[red\] that says "$1$" drawn in table - d\_dots: a Math \[red\] that says "$dots$" drawn in table - d\_row\_math: a Math \[text\] that says "$d\_j = 1 - c(j, j)$" - diag\_dots: a Math \[gray\] that says "$dots$" drawn in table - enum: a Math \[text\] that says "$P\_1, P\_2, P\_3, P\_4, dots$" - final: a Math \[text\] that says "$c(k, k) eq.not c(k, k)$" - grid\_cells: a Math \[text\] that says "$1$" drawn in table - grid\_cells\_10: a Math \[text\] that says "$0$" drawn in table - grid\_cells\_11: a Math \[text\] that says "$1$" drawn in table - grid\_cells\_12: a Math \[text\] that says "$1$" drawn in table - grid\_cells\_13: a Math \[text\] that says "$1$" drawn in table - grid\_cells\_14: a Math \[text\] that says "$0$" drawn in table - grid\_cells\_15: a Math \[text\] that says "$0$" drawn in table - grid\_cells\_16: a Math \[text\] that says "$0$" drawn in table - grid\_cells\_2: a Math \[text\] that says "$0$" drawn in table - grid\_cells\_3: a Math \[text\] that says "$1$" drawn in table - grid\_cells\_4: a Math \[text\] that says "$1$" drawn in table - grid\_cells\_5: a Math \[text\] that says "$1$" drawn in table - grid\_cells\_6: a Math \[text\] that says "$1$" drawn in table - grid\_cells\_7: a Math \[text\] that says "$0$" drawn in table - grid\_cells\_8: a Math \[text\] that says "$0$" drawn in table - grid\_cells\_9: a Math \[text\] that says "$0$" drawn in table - guide: a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True) - h\_note: a Panel that says "Decidable means one program answers every instance, correctly, in finite time." - h\_sig: a Math \[text\] that says "$H(P\_i, P\_j) = c(i, j)$" - head\_clash: a Heading that says "The Cell That Cannot Decide" - head\_d: a Heading that says "The Contrary Program" - head\_h: a Heading that says "Assume the Decider Exists" - head\_table: a Heading that says "Every Program Is on a List" - head\_theorem: a Heading that says "The Halting Problem" - input\_label: a Math \[gray\] that says "$upright("input")$" drawn in table - k\_line: a Math \[text\] that says "$D = P\_k quad upright("for some ") k$" - machine\_label: a Math \[gray\] that says "$upright("machine")$" drawn in table - point: a Point \[yellow\] drawn in table (location=(6.2, 3.8)) - point\_2: a Point \[yellow\] drawn in table (location=(4.7, 2.75)) - row\_d: a Math \[red\] that says "$D$" drawn in table - row\_dots: a Math \[gray\] that says "$dots$" drawn in table - row\_labels: a Math \[gray\] that says "$P\_1$" drawn in table - row\_labels\_2: a Math \[gray\] that says "$P\_2$" drawn in table - row\_labels\_3: a Math \[gray\] that says "$P\_3$" drawn in table - row\_labels\_4: a Math \[gray\] that says "$P\_4$" drawn in table - table: a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)) - theorem: a Math \[text\] that says "$H upright(" does not exist")$" - theorem\_note: a Panel that says "No program takes an arbitrary program and an arbitrary input and always reports correctly whether it halts." #### Beats ##### [03:51.284](https://academa.ai/lectures/halting-problem-undecidability?t=231.28431249999997) Narration: 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. Board: Empty. Actions: - [03:51.284](https://academa.ai/lectures/halting-problem-undecidability?t=231.28431249999997): head\_table is shown on the screen, written out. - [03:51.284](https://academa.ai/lectures/halting-problem-undecidability?t=231.28431249999997): table is shown on the screen, written out. - [04:9.988](https://academa.ai/lectures/halting-problem-undecidability?t=249.98831249999998): table moves to a new place on the board. - [04:9.988](https://academa.ai/lectures/halting-problem-undecidability?t=249.98831249999998): enum is shown on the screen, written out. ##### [04:12.295](https://academa.ai/lectures/halting-problem-undecidability?t=252.29481249999998) Narration: 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. Board: enum — a Math \[text\] that says "$P\_1, P\_2, P\_3, P\_4, dots$"; table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); head\_table — a Heading that says "Every Program Is on a List" Actions: - [04:12.643](https://academa.ai/lectures/halting-problem-undecidability?t=252.64331249999998): row\_labels is shown on the screen, written out. - [04:13.502](https://academa.ai/lectures/halting-problem-undecidability?t=253.50231249999996): row\_labels\_2 is shown on the screen, written out. - [04:14.303](https://academa.ai/lectures/halting-problem-undecidability?t=254.30331249999998): row\_labels\_3 is shown on the screen, written out. - [04:15.046](https://academa.ai/lectures/halting-problem-undecidability?t=255.04631249999997): row\_labels\_4 is shown on the screen, written out. - [04:16.544](https://academa.ai/lectures/halting-problem-undecidability?t=256.5443125): row\_dots is shown on the screen, written out. - [04:21.78](https://academa.ai/lectures/halting-problem-undecidability?t=261.7803125): machine\_label is shown on the screen, written out. ##### [04:31.68](https://academa.ai/lectures/halting-problem-undecidability?t=271.68031249999996) Narration: 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. Board: enum — a Math \[text\] that says "$P\_1, P\_2, P\_3, P\_4, dots$"; table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); head\_table — a Heading that says "Every Program Is on a List"; row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table Actions: - [04:32.086](https://academa.ai/lectures/halting-problem-undecidability?t=272.08631249999996): input\_label is shown on the screen, written out. - [04:42.315](https://academa.ai/lectures/halting-problem-undecidability?t=282.3153125): col\_heads is shown on the screen, written out. - [04:42.495](https://academa.ai/lectures/halting-problem-undecidability?t=282.49531249999995): col\_heads\_2 is shown on the screen, written out. - [04:42.675](https://academa.ai/lectures/halting-problem-undecidability?t=282.67531249999996): col\_heads\_3 is shown on the screen, written out. - [04:42.855](https://academa.ai/lectures/halting-problem-undecidability?t=282.85531249999997): col\_heads\_4 is shown on the screen, written out. - [04:43.035](https://academa.ai/lectures/halting-problem-undecidability?t=283.0353125): col\_dots is shown on the screen, written out. ##### [04:47.118](https://academa.ai/lectures/halting-problem-undecidability?t=287.11781249999996) Narration: 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. Board: enum — a Math \[text\] that says "$P\_1, P\_2, P\_3, P\_4, dots$"; table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); head\_table — a Heading that says "Every Program Is on a List"; row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table Actions: - [04:49.382](https://academa.ai/lectures/halting-problem-undecidability?t=289.38231249999995): cell\_def is shown on the screen, written out. - [04:56.522](https://academa.ai/lectures/halting-problem-undecidability?t=296.5223125): bit\_def is shown on the screen, written out. ##### [05:2.561](https://academa.ai/lectures/halting-problem-undecidability?t=302.5613125) Narration: 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. Board: enum — a Math \[text\] that says "$P\_1, P\_2, P\_3, P\_4, dots$"; cell\_def — a Math \[text\] that says "$c(i, j) = P\_i upright(" on ") P\_j$"; bit\_def — a Math \[text\] that says "$1 = upright("halts"), quad 0 = upright("loops")$"; table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); head\_table — a Heading that says "Every Program Is on a List"; row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table Actions: - [05:3.182](https://academa.ai/lectures/halting-problem-undecidability?t=303.18231249999997): grid\_cells is shown on the screen, written out. - [05:3.262](https://academa.ai/lectures/halting-problem-undecidability?t=303.2623125): grid\_cells\_2 is shown on the screen, written out. - [05:3.342](https://academa.ai/lectures/halting-problem-undecidability?t=303.3423125): grid\_cells\_3 is shown on the screen, written out. - [05:3.422](https://academa.ai/lectures/halting-problem-undecidability?t=303.4223125): grid\_cells\_4 is shown on the screen, written out. - [05:3.502](https://academa.ai/lectures/halting-problem-undecidability?t=303.50231249999996): grid\_cells\_5 is shown on the screen, written out. - [05:3.582](https://academa.ai/lectures/halting-problem-undecidability?t=303.5823125): grid\_cells\_6 is shown on the screen, written out. - [05:3.662](https://academa.ai/lectures/halting-problem-undecidability?t=303.6623125): grid\_cells\_7 is shown on the screen, written out. - [05:3.742](https://academa.ai/lectures/halting-problem-undecidability?t=303.74231249999997): grid\_cells\_8 is shown on the screen, written out. - [05:3.822](https://academa.ai/lectures/halting-problem-undecidability?t=303.82231249999995): grid\_cells\_9 is shown on the screen, written out. - [05:3.902](https://academa.ai/lectures/halting-problem-undecidability?t=303.9023125): grid\_cells\_10 is shown on the screen, written out. - [05:3.982](https://academa.ai/lectures/halting-problem-undecidability?t=303.9823125): grid\_cells\_11 is shown on the screen, written out. - [05:4.062](https://academa.ai/lectures/halting-problem-undecidability?t=304.06231249999996): grid\_cells\_12 is shown on the screen, written out. - [05:4.142](https://academa.ai/lectures/halting-problem-undecidability?t=304.1423125): grid\_cells\_13 is shown on the screen, written out. - [05:4.222](https://academa.ai/lectures/halting-problem-undecidability?t=304.2223125): grid\_cells\_14 is shown on the screen, written out. - [05:4.302](https://academa.ai/lectures/halting-problem-undecidability?t=304.30231249999997): grid\_cells\_15 is shown on the screen, written out. - [05:4.382](https://academa.ai/lectures/halting-problem-undecidability?t=304.3823125): grid\_cells\_16 is shown on the screen, written out. - [05:4.462](https://academa.ai/lectures/halting-problem-undecidability?t=304.4623125): diag\_dots is shown on the screen, written out. - [05:7.258](https://academa.ai/lectures/halting-problem-undecidability?t=307.2583125): grid\_cells is indicated — a transient flash. - [05:13.167](https://academa.ai/lectures/halting-problem-undecidability?t=313.1673125): grid\_cells\_2 is indicated — a transient flash. ##### [05:17.25](https://academa.ai/lectures/halting-problem-undecidability?t=317.25031249999995) Narration: 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. Board: enum — a Math \[text\] that says "$P\_1, P\_2, P\_3, P\_4, dots$"; cell\_def — a Math \[text\] that says "$c(i, j) = P\_i upright(" on ") P\_j$"; bit\_def — a Math \[text\] that says "$1 = upright("halts"), quad 0 = upright("loops")$"; table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); head\_table — a Heading that says "Every Program Is on a List"; row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table Actions: - [05:22.811](https://academa.ai/lectures/halting-problem-undecidability?t=322.8113125): point is shown on the screen, grown. - [05:24.811](https://academa.ai/lectures/halting-problem-undecidability?t=324.8113125): point is hidden from the screen. - [05:34.595](https://academa.ai/lectures/halting-problem-undecidability?t=334.5948125): bit\_def is hidden from the screen — left the board. - [05:34.595](https://academa.ai/lectures/halting-problem-undecidability?t=334.5948125): cell\_def is hidden from the screen — left the board. - [05:34.595](https://academa.ai/lectures/halting-problem-undecidability?t=334.5948125): enum is hidden from the screen — left the board. - [05:34.595](https://academa.ai/lectures/halting-problem-undecidability?t=334.5948125): head\_table is hidden from the screen — left the board. ##### [05:35.195](https://academa.ai/lectures/halting-problem-undecidability?t=335.1948125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table Actions: - [05:35.195](https://academa.ai/lectures/halting-problem-undecidability?t=335.1948125): head\_h is shown on the screen, written out. - [05:38.655](https://academa.ai/lectures/halting-problem-undecidability?t=338.6553125): h\_sig is shown on the screen, written out. - [05:48.291](https://academa.ai/lectures/halting-problem-undecidability?t=348.2913125): point\_2 is shown on the screen, grown. - [05:50.291](https://academa.ai/lectures/halting-problem-undecidability?t=350.2913125): point\_2 is hidden from the screen. ##### [05:51.294](https://academa.ai/lectures/halting-problem-undecidability?t=351.2943125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; h\_sig — a Math \[text\] that says "$H(P\_i, P\_j) = c(i, j)$"; head\_h — a Heading that says "Assume the Decider Exists" Actions: - [05:53.175](https://academa.ai/lectures/halting-problem-undecidability?t=353.1753125): h\_note is shown on the screen, written out. ##### [06:8.903](https://academa.ai/lectures/halting-problem-undecidability?t=368.90331249999997) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; h\_sig — a Math \[text\] that says "$H(P\_i, P\_j) = c(i, j)$"; h\_note — a Panel that says "Decidable means one program answers every instance, correctly, in finite time."; head\_h — a Heading that says "Assume the Decider Exists" Actions: - [06:10.145](https://academa.ai/lectures/halting-problem-undecidability?t=370.14531250000005): guide is shown on the screen, drawn. - [06:17.332](https://academa.ai/lectures/halting-problem-undecidability?t=377.33231250000006): grid\_cells is indicated — a transient flash. - [06:18.946](https://academa.ai/lectures/halting-problem-undecidability?t=378.94631250000003): grid\_cells\_6 is indicated — a transient flash. - [06:20.525](https://academa.ai/lectures/halting-problem-undecidability?t=380.52531250000004): grid\_cells\_11 is indicated — a transient flash. - [06:22.034](https://academa.ai/lectures/halting-problem-undecidability?t=382.03431250000006): grid\_cells\_16 is indicated — a transient flash. ##### [06:23.493](https://academa.ai/lectures/halting-problem-undecidability?t=383.4933125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; h\_sig — a Math \[text\] that says "$H(P\_i, P\_j) = c(i, j)$"; h\_note — a Panel that says "Decidable means one program answers every instance, correctly, in finite time."; head\_h — a Heading that says "Assume the Decider Exists"; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True) Actions: - [06:28.137](https://academa.ai/lectures/halting-problem-undecidability?t=388.1373125): guide is indicated — a transient flash. - [06:35.092](https://academa.ai/lectures/halting-problem-undecidability?t=395.0918125): h\_note is hidden from the screen — left the board. - [06:35.092](https://academa.ai/lectures/halting-problem-undecidability?t=395.0918125): h\_sig is hidden from the screen — left the board. - [06:35.092](https://academa.ai/lectures/halting-problem-undecidability?t=395.0918125): head\_h is hidden from the screen — left the board. ##### [06:36.292](https://academa.ai/lectures/halting-problem-undecidability?t=396.2918125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True) Actions: - [06:36.292](https://academa.ai/lectures/halting-problem-undecidability?t=396.2918125): head\_d is shown on the screen, written out. - [06:47.53](https://academa.ai/lectures/halting-problem-undecidability?t=407.5303125): d0 is shown on the screen, written out. ##### [06:51.868](https://academa.ai/lectures/halting-problem-undecidability?t=411.8683125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); d0 — a Math \[text\] that says "$D(P): quad upright("ask ") H(P, P)$"; head\_d — a Heading that says "The Contrary Program" Actions: - [07:0.854](https://academa.ai/lectures/halting-problem-undecidability?t=420.8543125): d1 is shown on the screen, written out. - [07:4.917](https://academa.ai/lectures/halting-problem-undecidability?t=424.9173125): d2 is shown on the screen, written out. ##### [07:7.096](https://academa.ai/lectures/halting-problem-undecidability?t=427.0963125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); d0 — a Math \[text\] that says "$D(P): quad upright("ask ") H(P, P)$"; d1 — a Math \[text\] that says "$upright("halts") arrow.r D upright(" loops")$"; d2 — a Math \[text\] that says "$upright("loops") arrow.r D upright(" halts")$"; head\_d — a Heading that says "The Contrary Program" Actions: - [07:9.941](https://academa.ai/lectures/halting-problem-undecidability?t=429.9413125): d0 is indicated — a transient flash. - [07:10.66](https://academa.ai/lectures/halting-problem-undecidability?t=430.66031250000003): d1 is indicated — a transient flash. ##### [07:21.216](https://academa.ai/lectures/halting-problem-undecidability?t=441.21581249999997) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [07:22.847](https://academa.ai/lectures/halting-problem-undecidability?t=442.8473125): row\_d is shown on the screen, written out. - [07:28.141](https://academa.ai/lectures/halting-problem-undecidability?t=448.1413125): grid\_cells is indicated — a transient flash. - [07:35.85](https://academa.ai/lectures/halting-problem-undecidability?t=455.8503125): d\_cells is shown on the screen, written out. ##### [07:37.321](https://academa.ai/lectures/halting-problem-undecidability?t=457.3208125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); d0 — a Math \[text\] that says "$D(P): quad upright("ask ") H(P, P)$"; d1 — a Math \[text\] that says "$upright("halts") arrow.r D upright(" loops")$"; d2 — a Math \[text\] that says "$upright("loops") arrow.r D upright(" halts")$"; head\_d — a Heading that says "The Contrary Program"; row\_d — a Math \[red\] that says "$D$" drawn in table; d\_cells — a Math \[red\] that says "$0$" drawn in table Actions: - [07:38.087](https://academa.ai/lectures/halting-problem-undecidability?t=458.0873125): grid\_cells\_6 is indicated — a transient flash. - [07:43.161](https://academa.ai/lectures/halting-problem-undecidability?t=463.1613125): d\_cells\_2 is shown on the screen, written out. - [07:44.856](https://academa.ai/lectures/halting-problem-undecidability?t=464.8563125): grid\_cells\_11 is indicated — a transient flash. - [07:46.725](https://academa.ai/lectures/halting-problem-undecidability?t=466.7253125): d\_cells\_3 is shown on the screen, written out. - [07:48.594](https://academa.ai/lectures/halting-problem-undecidability?t=468.5943125): grid\_cells\_16 is indicated — a transient flash. - [07:54.26](https://academa.ai/lectures/halting-problem-undecidability?t=474.2603125): d\_cells\_4 is shown on the screen, written out. ##### [07:55.661](https://academa.ai/lectures/halting-problem-undecidability?t=475.6613125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); d0 — a Math \[text\] that says "$D(P): quad upright("ask ") H(P, P)$"; d1 — a Math \[text\] that says "$upright("halts") arrow.r D upright(" loops")$"; d2 — a Math \[text\] that says "$upright("loops") arrow.r D upright(" halts")$"; head\_d — a Heading that says "The Contrary Program"; row\_d — a Math \[red\] that says "$D$" drawn in table; d\_cells — a Math \[red\] that says "$0$" drawn in table; d\_cells\_2 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_3 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_4 — a Math \[red\] that says "$1$" drawn in table Actions: - [08:0.502](https://academa.ai/lectures/halting-problem-undecidability?t=480.50231249999996): d\_row\_math is shown on the screen, written out. - [08:0.502](https://academa.ai/lectures/halting-problem-undecidability?t=480.50231249999996): d\_dots is shown on the screen, written out. - [08:9.291](https://academa.ai/lectures/halting-problem-undecidability?t=489.2913125): guide is indicated — a transient flash. - [08:12.322](https://academa.ai/lectures/halting-problem-undecidability?t=492.32181249999996): d0 is hidden from the screen — left the board. - [08:12.322](https://academa.ai/lectures/halting-problem-undecidability?t=492.32181249999996): d1 is hidden from the screen — left the board. - [08:12.322](https://academa.ai/lectures/halting-problem-undecidability?t=492.32181249999996): d2 is hidden from the screen — left the board. - [08:12.322](https://academa.ai/lectures/halting-problem-undecidability?t=492.32181249999996): d\_row\_math is hidden from the screen — left the board. - [08:12.322](https://academa.ai/lectures/halting-problem-undecidability?t=492.32181249999996): head\_d is hidden from the screen — left the board. ##### [08:13.522](https://academa.ai/lectures/halting-problem-undecidability?t=493.5218125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); row\_d — a Math \[red\] that says "$D$" drawn in table; d\_cells — a Math \[red\] that says "$0$" drawn in table; d\_cells\_2 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_3 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_4 — a Math \[red\] that says "$1$" drawn in table; d\_dots — a Math \[red\] that says "$dots$" drawn in table Actions: - [08:13.522](https://academa.ai/lectures/halting-problem-undecidability?t=493.5218125): head\_clash is shown on the screen, written out. - [08:25.526](https://academa.ai/lectures/halting-problem-undecidability?t=505.5263125): k\_line is shown on the screen, written out. - [08:27.325](https://academa.ai/lectures/halting-problem-undecidability?t=507.3253125): row\_d becomes "$D = P\_k$". - [08:27.325](https://academa.ai/lectures/halting-problem-undecidability?t=507.3253125): col\_k is shown on the screen, written out. ##### [08:28.872](https://academa.ai/lectures/halting-problem-undecidability?t=508.87181250000003) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); row\_d — a Math \[red\] that says "$D$" drawn in table; d\_cells — a Math \[red\] that says "$0$" drawn in table; d\_cells\_2 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_3 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_4 — a Math \[red\] that says "$1$" drawn in table; d\_dots — a Math \[red\] that says "$dots$" drawn in table; k\_line — a Math \[text\] that says "$D = P\_k quad upright("for some ") k$"; head\_clash — a Heading that says "The Cell That Cannot Decide"; col\_k — a Math \[red\] that says "$P\_k$" drawn in table Actions: - [08:32.558](https://academa.ai/lectures/halting-problem-undecidability?t=512.5583124999999): row\_d is indicated — a transient flash. - [08:38.839](https://academa.ai/lectures/halting-problem-undecidability?t=518.8393125): col\_k is indicated — a transient flash. ##### [08:45.07](https://academa.ai/lectures/halting-problem-undecidability?t=525.0703125) Narration: 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? Board: Unchanged from the preceding beat in this scene. Actions: - [08:49.017](https://academa.ai/lectures/halting-problem-undecidability?t=529.0173125): clash is shown on the screen, written out. - [08:55.89](https://academa.ai/lectures/halting-problem-undecidability?t=535.8903125): clash is indicated — a transient flash. ##### [09:1.134](https://academa.ai/lectures/halting-problem-undecidability?t=541.1343125000001) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); row\_d — a Math \[red\] that says "$D$" drawn in table; d\_cells — a Math \[red\] that says "$0$" drawn in table; d\_cells\_2 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_3 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_4 — a Math \[red\] that says "$1$" drawn in table; d\_dots — a Math \[red\] that says "$dots$" drawn in table; k\_line — a Math \[text\] that says "$D = P\_k quad upright("for some ") k$"; head\_clash — a Heading that says "The Cell That Cannot Decide"; col\_k — a Math \[red\] that says "$P\_k$" drawn in table; clash — a Math \[red\] that says "$?$" drawn in table Actions: - [09:1.482](https://academa.ai/lectures/halting-problem-undecidability?t=541.4823125): c1 is shown on the screen, written out. ##### [09:17.309](https://academa.ai/lectures/halting-problem-undecidability?t=557.3088125) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); row\_d — a Math \[red\] that says "$D$" drawn in table; d\_cells — a Math \[red\] that says "$0$" drawn in table; d\_cells\_2 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_3 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_4 — a Math \[red\] that says "$1$" drawn in table; d\_dots — a Math \[red\] that says "$dots$" drawn in table; k\_line — a Math \[text\] that says "$D = P\_k quad upright("for some ") k$"; c1 — a Math \[text\] that says "$c(k, k) = 1 quad arrow.r quad D upright(" loops")$"; head\_clash — a Heading that says "The Cell That Cannot Decide"; col\_k — a Math \[red\] that says "$P\_k$" drawn in table; clash — a Math \[red\] that says "$?$" drawn in table Actions: - [09:17.639](https://academa.ai/lectures/halting-problem-undecidability?t=557.6393125000001): c2 is shown on the screen, written out. ##### [09:33.188](https://academa.ai/lectures/halting-problem-undecidability?t=573.1878125000001) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); row\_d — a Math \[red\] that says "$D$" drawn in table; d\_cells — a Math \[red\] that says "$0$" drawn in table; d\_cells\_2 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_3 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_4 — a Math \[red\] that says "$1$" drawn in table; d\_dots — a Math \[red\] that says "$dots$" drawn in table; k\_line — a Math \[text\] that says "$D = P\_k quad upright("for some ") k$"; c1 — a Math \[text\] that says "$c(k, k) = 1 quad arrow.r quad D upright(" loops")$"; c2 — a Math \[text\] that says "$c(k, k) = 0 quad arrow.r quad D upright(" halts")$"; head\_clash — a Heading that says "The Cell That Cannot Decide"; col\_k — a Math \[red\] that says "$P\_k$" drawn in table; clash — a Math \[red\] that says "$?$" drawn in table Actions: - [09:41.564](https://academa.ai/lectures/halting-problem-undecidability?t=581.5643125000001): c1 (the "c(k, k) = 1" part) is struck through — it is ruled out. - [09:41.864](https://academa.ai/lectures/halting-problem-undecidability?t=581.8643125000001): c2 (the "c(k, k) = 0" part) is struck through — it is ruled out. - [09:45.151](https://academa.ai/lectures/halting-problem-undecidability?t=585.1513125000001): final is shown on the screen, written out. ##### [09:47.458](https://academa.ai/lectures/halting-problem-undecidability?t=587.4583125000001) Narration: 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. Board: table — a Figure (x\_range=(0.4, 11.4), y\_range=(0.3, 7.7), aspect=(11.0, 7.4)); row\_labels — a Math \[gray\] that says "$P\_1$" drawn in table; row\_labels\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; row\_labels\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; row\_labels\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; row\_dots — a Math \[gray\] that says "$dots$" drawn in table; machine\_label — a Math \[gray\] that says "$upright("machine")$" drawn in table; col\_heads — a Math \[gray\] that says "$P\_1$" drawn in table; col\_heads\_2 — a Math \[gray\] that says "$P\_2$" drawn in table; col\_heads\_3 — a Math \[gray\] that says "$P\_3$" drawn in table; col\_heads\_4 — a Math \[gray\] that says "$P\_4$" drawn in table; col\_dots — a Math \[gray\] that says "$dots$" drawn in table; input\_label — a Math \[gray\] that says "$upright("input")$" drawn in table; grid\_cells — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_2 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_3 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_4 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_5 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_6 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_7 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_8 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_9 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_10 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_11 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_12 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_13 — a Math \[text\] that says "$1$" drawn in table; grid\_cells\_14 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_15 — a Math \[text\] that says "$0$" drawn in table; grid\_cells\_16 — a Math \[text\] that says "$0$" drawn in table; diag\_dots — a Math \[gray\] that says "$dots$" drawn in table; guide — a Line \[yellow\] drawn in table (start=(2.8, 6.18), end=(10.6, 0.72), dashed=True); row\_d — a Math \[red\] that says "$D$" drawn in table; d\_cells — a Math \[red\] that says "$0$" drawn in table; d\_cells\_2 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_3 — a Math \[red\] that says "$0$" drawn in table; d\_cells\_4 — a Math \[red\] that says "$1$" drawn in table; d\_dots — a Math \[red\] that says "$dots$" drawn in table; k\_line — a Math \[text\] that says "$D = P\_k quad upright("for some ") k$"; c1 — a Math \[text\] that says "$c(k, k) = 1 quad arrow.r quad D upright(" loops")$"; c2 — a Math \[text\] that says "$c(k, k) = 0 quad arrow.r quad D upright(" halts")$"; final — a Math \[text\] that says "$c(k, k) eq.not c(k, k)$"; head\_clash — a Heading that says "The Cell That Cannot Decide"; col\_k — a Math \[red\] that says "$P\_k$" drawn in table; clash — a Math \[red\] that says "$?$" drawn in table Actions: - [09:53.379](https://academa.ai/lectures/halting-problem-undecidability?t=593.3793125000002): k\_line is indicated — a transient flash. - [10:7.032](https://academa.ai/lectures/halting-problem-undecidability?t=607.0323125000002): final is indicated — a transient flash. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): c1 is hidden from the screen — left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): c2 is hidden from the screen — left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): final is hidden from the screen — left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): head\_clash is hidden from the screen — left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): k\_line is hidden from the screen — left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): table is hidden from the screen — left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): row\_labels is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): row\_labels\_2 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): row\_labels\_3 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): row\_labels\_4 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): row\_dots is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): machine\_label is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): col\_heads is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): col\_heads\_2 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): col\_heads\_3 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): col\_heads\_4 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): col\_dots is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): input\_label is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_2 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_3 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_4 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_5 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_6 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_7 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_8 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_9 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_10 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_11 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_12 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_13 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_14 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_15 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): grid\_cells\_16 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): diag\_dots is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): guide is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): row\_d is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): d\_cells is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): d\_cells\_2 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): d\_cells\_3 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): d\_cells\_4 is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): d\_dots is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): col\_k is hidden from the screen — table left the board. - [10:7.915](https://academa.ai/lectures/halting-problem-undecidability?t=607.9148125000002): clash is hidden from the screen — table left the board. ##### [10:9.115](https://academa.ai/lectures/halting-problem-undecidability?t=609.1148125000001) Narration: 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. Board: Empty. Actions: - [10:9.115](https://academa.ai/lectures/halting-problem-undecidability?t=609.1148125000001): head\_theorem is shown on the screen, written out. - [10:10.089](https://academa.ai/lectures/halting-problem-undecidability?t=610.0893125000001): theorem is shown on the screen, written out. - [10:15.744](https://academa.ai/lectures/halting-problem-undecidability?t=615.7443125000002): theorem\_note is shown on the screen, written out. - [10:24.904](https://academa.ai/lectures/halting-problem-undecidability?t=624.9043125000002): A box is drawn around theorem. - [10:26.302](https://academa.ai/lectures/halting-problem-undecidability?t=626.3016666666667): head\_theorem is hidden from the screen — left the board. - [10:26.302](https://academa.ai/lectures/halting-problem-undecidability?t=626.3016666666667): theorem is hidden from the screen — left the board. - [10:26.302](https://academa.ai/lectures/halting-problem-undecidability?t=626.3016666666667): theorem\_note is hidden from the screen — left the board. ### Scene 3: [Undecidable Is Not the Same as Expensive](https://academa.ai/lectures/halting-problem-undecidability?t=627.3433333333335) Span: 10:27.343–13:10.742 (627.3433333333335s–790.7419375000002s). #### Objects - a\_bounded: a Text \[text\] that says "Decidable. Simulate $N$ steps and look." - a\_ever: a Text \[text\] that says "Undecidable. There is no $N$ at which silence becomes an answer." - head\_collatz: a Heading that says "A Program Nobody Can Settle" - head\_cost: a Heading that says "Two Questions About One Program" - head\_moral: a Heading that says "Cost and Existence" - left\_label: a Tex \[text\] that says "A bounded question" - moral: a Panel that says "Complexity asks how long a procedure takes. Computability asks whether one exists. The proof never mentioned time." - moral\_math: a Math \[text\] that says "$upright("undecidable") eq.not upright("slow")$" - open\_note: a Panel that says "Checked for every start below $2^(68)$. Checking is not proving." - plot: an Axes (x\_range=(0.0, 115.0), y\_range=(0.0, 10000.0), x\_ticks\_every=25.0) - probe: a PlotPoint \[yellow\] drawn in plot (target='trace', x=\) - q\_bounded: a Math \[text\] that says "$P upright(" halts within ") N upright(" steps?")$" - q\_ever: a Math \[text\] that says "$P upright(" halts, ever?")$" - right\_label: a Tex \[text\] that says "The unbounded question" - rule\_text: a Text \[text\] that says "Even: halve it. Odd: triple it and add one. Stop at 1." - trace: a FunctionPlot \[blue\] drawn in plot (function=\, x\_range=(0.0, 111.0)) - walk: a VariableNumber #### Beats ##### [10:27.343](https://academa.ai/lectures/halting-problem-undecidability?t=627.3433333333335) Narration: 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. Board: Empty. Actions: - [10:27.343](https://academa.ai/lectures/halting-problem-undecidability?t=627.3433333333335): head\_cost is shown on the screen, written out. - [10:40.253](https://academa.ai/lectures/halting-problem-undecidability?t=640.2533333333334): left\_label is shown on the screen, written out. - [10:40.453](https://academa.ai/lectures/halting-problem-undecidability?t=640.4533333333335): right\_label is shown on the screen, written out. ##### [10:42.05](https://academa.ai/lectures/halting-problem-undecidability?t=642.0498333333335) Narration: 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. Board: left\_label — a Tex \[text\] that says "A bounded question"; right\_label — a Tex \[text\] that says "The unbounded question"; head\_cost — a Heading that says "Two Questions About One Program" Actions: - [10:43.942](https://academa.ai/lectures/halting-problem-undecidability?t=643.9423333333335): q\_bounded is shown on the screen, written out. - [10:48.934](https://academa.ai/lectures/halting-problem-undecidability?t=648.9343333333335): a\_bounded is shown on the screen, written out. ##### [10:59.31](https://academa.ai/lectures/halting-problem-undecidability?t=659.3098333333335) Narration: 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. Board: left\_label — a Tex \[text\] that says "A bounded question"; q\_bounded — a Math \[text\] that says "$P upright(" halts within ") N upright(" steps?")$"; a\_bounded — a Text \[text\] that says "Decidable. Simulate $N$ steps and look."; right\_label — a Tex \[text\] that says "The unbounded question"; head\_cost — a Heading that says "Two Questions About One Program" Actions: - [11:6.241](https://academa.ai/lectures/halting-problem-undecidability?t=666.2413333333335): a\_bounded is indicated — a transient flash. ##### [11:13.261](https://academa.ai/lectures/halting-problem-undecidability?t=673.2613333333335) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [11:15.026](https://academa.ai/lectures/halting-problem-undecidability?t=675.0263333333335): q\_ever is shown on the screen, written out. - [11:24.198](https://academa.ai/lectures/halting-problem-undecidability?t=684.1983333333335): a\_ever is shown on the screen, written out. ##### [11:27.956](https://academa.ai/lectures/halting-problem-undecidability?t=687.9563333333335) Narration: 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. Board: left\_label — a Tex \[text\] that says "A bounded question"; q\_bounded — a Math \[text\] that says "$P upright(" halts within ") N upright(" steps?")$"; a\_bounded — a Text \[text\] that says "Decidable. Simulate $N$ steps and look."; right\_label — a Tex \[text\] that says "The unbounded question"; q\_ever — a Math \[text\] that says "$P upright(" halts, ever?")$"; a\_ever — a Text \[text\] that says "Undecidable. There is no $N$ at which silence becomes an answer."; head\_cost — a Heading that says "Two Questions About One Program" Actions: - [11:29.883](https://academa.ai/lectures/halting-problem-undecidability?t=689.8833333333334): a\_ever (the "silence becomes an answer" part) is emphasized. - [11:32.089](https://academa.ai/lectures/halting-problem-undecidability?t=692.0893333333335): a\_ever (the "silence becomes an answer" part) is no longer emphasized. - [11:42.19](https://academa.ai/lectures/halting-problem-undecidability?t=702.1903333333335): q\_ever is indicated — a transient flash. - [11:43.27](https://academa.ai/lectures/halting-problem-undecidability?t=703.2698333333335): a\_bounded is hidden from the screen — left the board. - [11:43.27](https://academa.ai/lectures/halting-problem-undecidability?t=703.2698333333335): a\_ever is hidden from the screen — left the board. - [11:43.27](https://academa.ai/lectures/halting-problem-undecidability?t=703.2698333333335): head\_cost is hidden from the screen — left the board. - [11:43.27](https://academa.ai/lectures/halting-problem-undecidability?t=703.2698333333335): left\_label is hidden from the screen — left the board. - [11:43.27](https://academa.ai/lectures/halting-problem-undecidability?t=703.2698333333335): q\_bounded is hidden from the screen — left the board. - [11:43.27](https://academa.ai/lectures/halting-problem-undecidability?t=703.2698333333335): q\_ever is hidden from the screen — left the board. - [11:43.27](https://academa.ai/lectures/halting-problem-undecidability?t=703.2698333333335): right\_label is hidden from the screen — left the board. ##### [11:43.87](https://academa.ai/lectures/halting-problem-undecidability?t=703.8698333333334) Narration: 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. Board: Empty. Actions: - [11:43.87](https://academa.ai/lectures/halting-problem-undecidability?t=703.8698333333334): head\_collatz is shown on the screen, written out. - [11:43.87](https://academa.ai/lectures/halting-problem-undecidability?t=703.8698333333334): plot is shown on the screen, written out. - [11:48.722](https://academa.ai/lectures/halting-problem-undecidability?t=708.7223333333335): trace is shown on the screen, drawn. - [11:51.114](https://academa.ai/lectures/halting-problem-undecidability?t=711.1143333333334): plot moves to a new place on the board. - [11:51.114](https://academa.ai/lectures/halting-problem-undecidability?t=711.1143333333334): rule\_text is shown on the screen, written out. ##### [11:57.983](https://academa.ai/lectures/halting-problem-undecidability?t=717.9833333333335) Narration: 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. Board: rule\_text — a Text \[text\] that says "Even: halve it. Odd: triple it and add one. Stop at 1."; plot — an Axes (x\_range=(0.0, 115.0), y\_range=(0.0, 10000.0), x\_ticks\_every=25.0); head\_collatz — a Heading that says "A Program Nobody Can Settle"; trace — a FunctionPlot \[blue\] drawn in plot (function=\, x\_range=(0.0, 111.0)) Actions: - [11:58.285](https://academa.ai/lectures/halting-problem-undecidability?t=718.2853333333335): probe is shown on the screen, written out. - [12:1.733](https://academa.ai/lectures/halting-problem-undecidability?t=721.7333333333335): probe is redrawn as the numbers it depends on change. - [12:1.733](https://academa.ai/lectures/halting-problem-undecidability?t=721.7333333333335): walk ticks to 111.0. ##### [12:9.462](https://academa.ai/lectures/halting-problem-undecidability?t=729.4618333333335) Narration: 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. Board: rule\_text — a Text \[text\] that says "Even: halve it. Odd: triple it and add one. Stop at 1."; plot — an Axes (x\_range=(0.0, 115.0), y\_range=(0.0, 10000.0), x\_ticks\_every=25.0); head\_collatz — a Heading that says "A Program Nobody Can Settle"; trace — a FunctionPlot \[blue\] drawn in plot (function=\, x\_range=(0.0, 111.0)); probe — a PlotPoint \[yellow\] drawn in plot (target='trace', x=\) Actions: - [12:16.614](https://academa.ai/lectures/halting-problem-undecidability?t=736.6143333333334): open\_note is shown on the screen, written out. ##### [12:21.916](https://academa.ai/lectures/halting-problem-undecidability?t=741.9158333333335) Narration: 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. Board: rule\_text — a Text \[text\] that says "Even: halve it. Odd: triple it and add one. Stop at 1."; open\_note — a Panel that says "Checked for every start below $2^(68)$. Checking is not proving."; plot — an Axes (x\_range=(0.0, 115.0), y\_range=(0.0, 10000.0), x\_ticks\_every=25.0); head\_collatz — a Heading that says "A Program Nobody Can Settle"; trace — a FunctionPlot \[blue\] drawn in plot (function=\, x\_range=(0.0, 111.0)); probe — a PlotPoint \[yellow\] drawn in plot (target='trace', x=\) Actions: - [12:30.704](https://academa.ai/lectures/halting-problem-undecidability?t=750.7043333333335): trace is indicated — a transient flash. - [12:39.76](https://academa.ai/lectures/halting-problem-undecidability?t=759.7603333333335): head\_collatz is hidden from the screen — left the board. - [12:39.76](https://academa.ai/lectures/halting-problem-undecidability?t=759.7603333333335): open\_note is hidden from the screen — left the board. - [12:39.76](https://academa.ai/lectures/halting-problem-undecidability?t=759.7603333333335): plot is hidden from the screen — left the board. - [12:39.76](https://academa.ai/lectures/halting-problem-undecidability?t=759.7603333333335): trace is hidden from the screen — plot left the board. - [12:39.76](https://academa.ai/lectures/halting-problem-undecidability?t=759.7603333333335): probe is hidden from the screen — plot left the board. - [12:39.76](https://academa.ai/lectures/halting-problem-undecidability?t=759.7603333333335): rule\_text is hidden from the screen — left the board. ##### [12:40.96](https://academa.ai/lectures/halting-problem-undecidability?t=760.9603333333334) Narration: 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. Board: Empty. Actions: - [12:40.96](https://academa.ai/lectures/halting-problem-undecidability?t=760.9603333333334): head\_moral is shown on the screen, written out. - [12:42.586](https://academa.ai/lectures/halting-problem-undecidability?t=762.5863333333334): moral\_math is shown on the screen, written out. - [12:43.758](https://academa.ai/lectures/halting-problem-undecidability?t=763.7583333333334): moral is shown on the screen, written out. ##### [12:56.607](https://academa.ai/lectures/halting-problem-undecidability?t=776.6068333333335) Narration: 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. Board: moral\_math — a Math \[text\] that says "$upright("undecidable") eq.not upright("slow")$"; moral — a Panel that says "Complexity asks how long a procedure takes. Computability asks whether one exists. The proof never mentioned time."; head\_moral — a Heading that says "Cost and Existence" Actions: - [13:6.928](https://academa.ai/lectures/halting-problem-undecidability?t=786.9283333333335): moral (the "The proof never mentioned time" part) is emphasized. - [13:7.636](https://academa.ai/lectures/halting-problem-undecidability?t=787.6363333333335): moral\_math is indicated — a transient flash. - [13:8.588](https://academa.ai/lectures/halting-problem-undecidability?t=788.5883333333335): moral (the "The proof never mentioned time" part) is no longer emphasized. - [13:9.7](https://academa.ai/lectures/halting-problem-undecidability?t=789.7002708333334): head\_moral is hidden from the screen — left the board. - [13:9.7](https://academa.ai/lectures/halting-problem-undecidability?t=789.7002708333334): moral is hidden from the screen — left the board. - [13:9.7](https://academa.ai/lectures/halting-problem-undecidability?t=789.7002708333334): moral\_math is hidden from the screen — left the board. ### Scene 4: [One More, by Reduction](https://academa.ai/lectures/halting-problem-undecidability?t=790.7419375000002) Span: 13:10.742–16:31.624 (790.7419375000002s–991.6238125000002s). #### Objects - arrow\_in: an Arrow \[gray\] drawn in pipeline (start=(1.75, 3.2), end=(2.55, 3.2)) - arrow\_mid: an Arrow \[gray\] drawn in pipeline (start=(5.55, 3.2), end=(6.35, 3.2)) - arrow\_out: an Arrow \[gray\] drawn in pipeline (start=(8.75, 3.2), end=(9.55, 3.2)) - box\_build: a Polygon \[green\] drawn in pipeline (vertices=((2.7, 2.3), (5.4, 2.3), (5.4, 4.1), (2.7, 4.1)), fill\_opacity=0.18) - box\_t: a Polygon \[blue\] drawn in pipeline (vertices=((6.5, 2.3), (8.6, 2.3), (8.6, 4.1), (6.5, 4.1)), fill\_opacity=0.18) - build\_def: a Math \[text\] that says "$M(y): quad upright("run ") P upright(" on ") x$" - build\_label: a Math \[green\] that says "$upright("build ") M$" drawn in pipeline - closing: a Panel that says "Diagonalise once. After that, reduce: show that a decider for the new question would build a decider for one we have already killed." - conclusion: a Math \[text\] that says "$T upright(" exists") arrow.r H upright(" exists")$" - head\_end: a Heading that says "The Technique" - head\_reduce: a Heading that says "Turning $T$ Into $H$" - head\_total: a Heading that says "A Second Question" - in\_label: a Math \[text\] that says "$(P, x)$" drawn in pipeline - out\_label: a Math \[text\] that says "$upright("yes or no")$" drawn in pipeline - pipeline: a Figure (x\_range=(0.0, 12.0), y\_range=(0.4, 6.4), aspect=(12.0, 6.0)) - r1: a Math \[text\] that says "$P upright(" halts") arrow.r M upright(" is total")$" - r2: a Math \[text\] that says "$P upright(" loops") arrow.r M upright(" halts on nothing")$" - shell: a Polygon \[red\] drawn in pipeline (vertices=((2.3000000000000003, 1.4999999999999998), (9.0, 1.499999999999…, filled=False, dashed=True) - shell\_label: a Math \[red\] that says "$H$" drawn in pipeline - t\_label: a Math \[blue\] that says "$T$" drawn in pipeline - total\_math: a Math \[text\] that says "$T(M): quad forall y, quad M upright(" halts on ") y$" - total\_q: a Panel that says "Does machine $M$ halt on every input? This is the totality problem." - verdict: a Math \[text\] that says "$upright("no ") H arrow.r upright("no ") T$" #### Beats ##### [13:10.742](https://academa.ai/lectures/halting-problem-undecidability?t=790.7419375000002) Narration: 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. Board: Empty. Actions: - [13:10.742](https://academa.ai/lectures/halting-problem-undecidability?t=790.7419375000002): head\_total is shown on the screen, written out. ##### [13:23.822](https://academa.ai/lectures/halting-problem-undecidability?t=803.8224375000002) Narration: 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. Board: head\_total — a Heading that says "A Second Question" Actions: - [13:26.412](https://academa.ai/lectures/halting-problem-undecidability?t=806.4119375000001): total\_math is shown on the screen, written out. - [13:35.468](https://academa.ai/lectures/halting-problem-undecidability?t=815.4679375000002): total\_q is shown on the screen, written out. ##### [13:41.164](https://academa.ai/lectures/halting-problem-undecidability?t=821.1644375000002) Narration: 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. Board: total\_math — a Math \[text\] that says "$T(M): quad forall y, quad M upright(" halts on ") y$"; total\_q — a Panel that says "Does machine $M$ halt on every input? This is the totality problem."; head\_total — a Heading that says "A Second Question" Actions: - [13:47.41](https://academa.ai/lectures/halting-problem-undecidability?t=827.4099375000002): total\_math is indicated — a transient flash. - [13:58.022](https://academa.ai/lectures/halting-problem-undecidability?t=838.0219375000001): head\_total is hidden from the screen — left the board. - [13:58.022](https://academa.ai/lectures/halting-problem-undecidability?t=838.0219375000001): total\_math is hidden from the screen — left the board. - [13:58.022](https://academa.ai/lectures/halting-problem-undecidability?t=838.0219375000001): total\_q is hidden from the screen — left the board. ##### [13:59.222](https://academa.ai/lectures/halting-problem-undecidability?t=839.2219375000002) Narration: 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. Board: Empty. Actions: - [13:59.222](https://academa.ai/lectures/halting-problem-undecidability?t=839.2219375000002): head\_reduce is shown on the screen, written out. - [13:59.222](https://academa.ai/lectures/halting-problem-undecidability?t=839.2219375000002): pipeline is shown on the screen, written out. - [14:4.795](https://academa.ai/lectures/halting-problem-undecidability?t=844.7949375000002): in\_label is shown on the screen, written out. - [14:9.392](https://academa.ai/lectures/halting-problem-undecidability?t=849.3919375000002): arrow\_in is shown on the screen, written out. - [14:9.392](https://academa.ai/lectures/halting-problem-undecidability?t=849.3919375000002): box\_build is shown on the screen, written out. - [14:9.392](https://academa.ai/lectures/halting-problem-undecidability?t=849.3919375000002): build\_label is shown on the screen, written out. - [14:9.915](https://academa.ai/lectures/halting-problem-undecidability?t=849.9149375000002): build\_def is shown on the screen, written out. ##### [14:12.558](https://academa.ai/lectures/halting-problem-undecidability?t=852.5584375000002) Narration: 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. Board: build\_def — a Math \[text\] that says "$M(y): quad upright("run ") P upright(" on ") x$"; pipeline — a Figure (x\_range=(0.0, 12.0), y\_range=(0.4, 6.4), aspect=(12.0, 6.0)); head\_reduce — a Heading that says "Turning $T$ Into $H$"; in\_label — a Math \[text\] that says "$(P, x)$" drawn in pipeline; arrow\_in — an Arrow \[gray\] drawn in pipeline (start=(1.75, 3.2), end=(2.55, 3.2)); box\_build — a Polygon \[green\] drawn in pipeline (vertices=((2.7, 2.3), (5.4, 2.3), (5.4, 4.1), (2.7, 4.1)), fill\_opacity=0.18); build\_label — a Math \[green\] that says "$upright("build ") M$" drawn in pipeline Actions: - [14:14.439](https://academa.ai/lectures/halting-problem-undecidability?t=854.4389375000002): build\_def is indicated — a transient flash. - [14:24.76](https://academa.ai/lectures/halting-problem-undecidability?t=864.7599375000002): box\_build is indicated — a transient flash. ##### [14:27.81](https://academa.ai/lectures/halting-problem-undecidability?t=867.8104375000001) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [14:32.501](https://academa.ai/lectures/halting-problem-undecidability?t=872.5009375000002): build\_def (the "upright("run ") P upright(" on ") x" part) is emphasized. - [14:38.758](https://academa.ai/lectures/halting-problem-undecidability?t=878.7579375000001): build\_def (the "upright("run ") P upright(" on ") x" part) is no longer emphasized. ##### [14:40.867](https://academa.ai/lectures/halting-problem-undecidability?t=880.8674375000002) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [14:49.982](https://academa.ai/lectures/halting-problem-undecidability?t=889.9819375000002): r1 is shown on the screen, written out. - [14:55.996](https://academa.ai/lectures/halting-problem-undecidability?t=895.9959375000002): r2 is shown on the screen, written out. ##### [14:57.652](https://academa.ai/lectures/halting-problem-undecidability?t=897.6524375000001) Narration: 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. Board: build\_def — a Math \[text\] that says "$M(y): quad upright("run ") P upright(" on ") x$"; r1 — a Math \[text\] that says "$P upright(" halts") arrow.r M upright(" is total")$"; r2 — a Math \[text\] that says "$P upright(" loops") arrow.r M upright(" halts on nothing")$"; pipeline — a Figure (x\_range=(0.0, 12.0), y\_range=(0.4, 6.4), aspect=(12.0, 6.0)); head\_reduce — a Heading that says "Turning $T$ Into $H$"; in\_label — a Math \[text\] that says "$(P, x)$" drawn in pipeline; arrow\_in — an Arrow \[gray\] drawn in pipeline (start=(1.75, 3.2), end=(2.55, 3.2)); box\_build — a Polygon \[green\] drawn in pipeline (vertices=((2.7, 2.3), (5.4, 2.3), (5.4, 4.1), (2.7, 4.1)), fill\_opacity=0.18); build\_label — a Math \[green\] that says "$upright("build ") M$" drawn in pipeline Actions: - [14:58.233](https://academa.ai/lectures/halting-problem-undecidability?t=898.2329375000002): arrow\_mid is shown on the screen, written out. - [14:58.233](https://academa.ai/lectures/halting-problem-undecidability?t=898.2329375000002): box\_t is shown on the screen, written out. - [14:58.233](https://academa.ai/lectures/halting-problem-undecidability?t=898.2329375000002): t\_label is shown on the screen, written out. - [15:9.099](https://academa.ai/lectures/halting-problem-undecidability?t=909.0989375000001): arrow\_out is shown on the screen, written out. - [15:9.099](https://academa.ai/lectures/halting-problem-undecidability?t=909.0989375000001): out\_label is shown on the screen, written out. ##### [15:12.863](https://academa.ai/lectures/halting-problem-undecidability?t=912.8629375000002) Narration: 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. Board: build\_def — a Math \[text\] that says "$M(y): quad upright("run ") P upright(" on ") x$"; r1 — a Math \[text\] that says "$P upright(" halts") arrow.r M upright(" is total")$"; r2 — a Math \[text\] that says "$P upright(" loops") arrow.r M upright(" halts on nothing")$"; pipeline — a Figure (x\_range=(0.0, 12.0), y\_range=(0.4, 6.4), aspect=(12.0, 6.0)); head\_reduce — a Heading that says "Turning $T$ Into $H$"; in\_label — a Math \[text\] that says "$(P, x)$" drawn in pipeline; arrow\_in — an Arrow \[gray\] drawn in pipeline (start=(1.75, 3.2), end=(2.55, 3.2)); box\_build — a Polygon \[green\] drawn in pipeline (vertices=((2.7, 2.3), (5.4, 2.3), (5.4, 4.1), (2.7, 4.1)), fill\_opacity=0.18); build\_label — a Math \[green\] that says "$upright("build ") M$" drawn in pipeline; arrow\_mid — an Arrow \[gray\] drawn in pipeline (start=(5.55, 3.2), end=(6.35, 3.2)); box\_t — a Polygon \[blue\] drawn in pipeline (vertices=((6.5, 2.3), (8.6, 2.3), (8.6, 4.1), (6.5, 4.1)), fill\_opacity=0.18); t\_label — a Math \[blue\] that says "$T$" drawn in pipeline; arrow\_out — an Arrow \[gray\] drawn in pipeline (start=(8.75, 3.2), end=(9.55, 3.2)); out\_label — a Math \[text\] that says "$upright("yes or no")$" drawn in pipeline Actions: - [15:15.179](https://academa.ai/lectures/halting-problem-undecidability?t=915.1789375000002): shell is shown on the screen, written out. - [15:16.398](https://academa.ai/lectures/halting-problem-undecidability?t=916.3979375000001): shell\_label is shown on the screen, written out. - [15:21.112](https://academa.ai/lectures/halting-problem-undecidability?t=921.1119375000002): conclusion is shown on the screen, written out. - [15:28.809](https://academa.ai/lectures/halting-problem-undecidability?t=928.8094375000002): conclusion moves to a new place on the board. - [15:28.809](https://academa.ai/lectures/halting-problem-undecidability?t=928.8094375000002): r1 moves to a new place on the board. - [15:28.809](https://academa.ai/lectures/halting-problem-undecidability?t=928.8094375000002): r2 moves to a new place on the board. - [15:28.809](https://academa.ai/lectures/halting-problem-undecidability?t=928.8094375000002): build\_def is hidden from the screen — left the board. ##### [15:29.409](https://academa.ai/lectures/halting-problem-undecidability?t=929.4094375000002) Narration: 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. Board: r1 — a Math \[text\] that says "$P upright(" halts") arrow.r M upright(" is total")$"; r2 — a Math \[text\] that says "$P upright(" loops") arrow.r M upright(" halts on nothing")$"; conclusion — a Math \[text\] that says "$T upright(" exists") arrow.r H upright(" exists")$"; pipeline — a Figure (x\_range=(0.0, 12.0), y\_range=(0.4, 6.4), aspect=(12.0, 6.0)); head\_reduce — a Heading that says "Turning $T$ Into $H$"; in\_label — a Math \[text\] that says "$(P, x)$" drawn in pipeline; arrow\_in — an Arrow \[gray\] drawn in pipeline (start=(1.75, 3.2), end=(2.55, 3.2)); box\_build — a Polygon \[green\] drawn in pipeline (vertices=((2.7, 2.3), (5.4, 2.3), (5.4, 4.1), (2.7, 4.1)), fill\_opacity=0.18); build\_label — a Math \[green\] that says "$upright("build ") M$" drawn in pipeline; arrow\_mid — an Arrow \[gray\] drawn in pipeline (start=(5.55, 3.2), end=(6.35, 3.2)); box\_t — a Polygon \[blue\] drawn in pipeline (vertices=((6.5, 2.3), (8.6, 2.3), (8.6, 4.1), (6.5, 4.1)), fill\_opacity=0.18); t\_label — a Math \[blue\] that says "$T$" drawn in pipeline; arrow\_out — an Arrow \[gray\] drawn in pipeline (start=(8.75, 3.2), end=(9.55, 3.2)); out\_label — a Math \[text\] that says "$upright("yes or no")$" drawn in pipeline; shell — a Polygon \[red\] drawn in pipeline (vertices=((2.3000000000000003, 1.4999999999999998), (9.0, 1.499999999999…, filled=False, dashed=True); shell\_label — a Math \[red\] that says "$H$" drawn in pipeline Actions: - [15:32.265](https://academa.ai/lectures/halting-problem-undecidability?t=932.2649375000002): conclusion (the "H upright(" exists")" part) is emphasized. - [15:34.529](https://academa.ai/lectures/halting-problem-undecidability?t=934.5289375000002): shell\_label is indicated — a transient flash. - [15:39.034](https://academa.ai/lectures/halting-problem-undecidability?t=939.0339375000001): conclusion (the "H upright(" exists")" part) is no longer emphasized. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): conclusion is hidden from the screen — left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): head\_reduce is hidden from the screen — left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): pipeline is hidden from the screen — left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): in\_label is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): arrow\_in is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): box\_build is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): build\_label is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): arrow\_mid is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): box\_t is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): t\_label is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): arrow\_out is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): out\_label is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): shell is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): shell\_label is hidden from the screen — pipeline left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): r1 is hidden from the screen — left the board. - [15:43.805](https://academa.ai/lectures/halting-problem-undecidability?t=943.8054375000002): r2 is hidden from the screen — left the board. ##### [15:45.005](https://academa.ai/lectures/halting-problem-undecidability?t=945.0054375000002) Narration: 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. Board: Empty. Actions: - [15:45.005](https://academa.ai/lectures/halting-problem-undecidability?t=945.0054375000002): head\_end is shown on the screen, written out. - [15:51.495](https://academa.ai/lectures/halting-problem-undecidability?t=951.4949375000001): verdict is shown on the screen, written out. ##### [16:0.617](https://academa.ai/lectures/halting-problem-undecidability?t=960.6174375000002) Narration: 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. Board: verdict — a Math \[text\] that says "$upright("no ") H arrow.r upright("no ") T$"; head\_end — a Heading that says "The Technique" Actions: - [16:1.407](https://academa.ai/lectures/halting-problem-undecidability?t=961.4069375000001): closing is shown on the screen, written out. ##### [16:16.241](https://academa.ai/lectures/halting-problem-undecidability?t=976.2409375000002) Narration: 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. Board: verdict — a Math \[text\] that says "$upright("no ") H arrow.r upright("no ") T$"; closing — a Panel that says "Diagonalise once. After that, reduce: show that a decider for the new question would build a decider for one we have already killed."; head\_end — a Heading that says "The Technique" Actions: - [16:22.522](https://academa.ai/lectures/halting-problem-undecidability?t=982.5219375000001): A box is drawn around verdict. - [16:24.856](https://academa.ai/lectures/halting-problem-undecidability?t=984.8559375000002): closing (the "Diagonalise once" part) is emphasized. - [16:29.082](https://academa.ai/lectures/halting-problem-undecidability?t=989.0819375000001): closing (the "Diagonalise once" part) is no longer emphasized. - [16:30.582](https://academa.ai/lectures/halting-problem-undecidability?t=990.5821458333335): closing is hidden from the screen — left the board. - [16:30.582](https://academa.ai/lectures/halting-problem-undecidability?t=990.5821458333335): head\_end is hidden from the screen — left the board. - [16:30.582](https://academa.ai/lectures/halting-problem-undecidability?t=990.5821458333335): verdict is hidden from the screen — left the board.