▶︎ 0:02 Today, I want to talk about computation. And I say computation, probably that sounds like it has something to do with computers. And in a way it does, but really, computation is a fundamental concept, really part of the mysteries of the universe that transcends any particular technology.
▶︎ 0:19 For example, if you showed me some alien civilization on a different planet, I wouldn't be surprised if they had also computers, but that the computers somehow worked in some sense rather differently than ours. That wouldn't surprise me. But I would bet a lot of money that that alien civilization discovered exactly the same notion of computation that we're going to be talking about today. So you can start the story of computation
▶︎ 0:48 at many different points in time. I've decided to start the story in 1936. So why 1936? Because that's the year that Alan Turing published his landmark paper on Computable Numbers with an Application to the, and please forgive my German, Entscheidungsproblem.
▶︎ 1:09 Now, if the name Alan Turing sounds familiar, there's a few different reasons why that might be true. Maybe you've heard of the Turing test. The Turing test is something Alan Turing proposed a long time ago, maybe 75 years ago. He was already very interested in the idea of artificial intelligence, and he proposed the Turing test as when a computer, when software would have achieved what he thought should be called artificial intelligence or AI. Namely, that once a computer was capable of conversing with a human, and that human could not differentiate whether they were speaking to a computer or to another human, that would be passing the Turing test. So Turing proposed that as one criterion for what should qualify as artificial intelligence. And definitely, this decade, there's no question, modern AI has indeed passed that Turing test.
▶︎ 2:01 Maybe you've heard of Alan Turing because of his code-breaking work that he did in World War II, at Bletchley Park. Maybe you heard about Alan Turing because of his persecution by, and later posthumous pardon, by the British government for homosexuality. Maybe you saw parts of these various stories in the semi-accurate movie, The Imitation Game. In any case, if you've seen any of those things, this is exactly the same Alan Turing.
▶︎ 2:28 So it's been cool to watch, actually, over my lifetime, the name recognition for Alan Turing to grow. That's been great. I will say, computer scientists such as myself, we tend to think that Alan Turing's name should be as widely known as, for example, Albert Einstein. So we're not quite there yet, but there's been progress over the last couple of decades, which has been cool to see.
▶︎ 2:50 Back to Turing's 1936 paper. What's so important about it? Well honestly, many computer scientists, like myself, view Turing's 1936 paper as literally the birth of computer science, as a scientific discipline. So if that sounds like a big deal, indeed, that's a pretty big deal.
▶︎ 3:09 A couple of things that are kind of wild about this fact. First of all, 1936, that was before we really had computers in any form that we would now understand them. The first real serious efforts to build general-purpose computers were gonna be pretty much a decade later, more or less in the late '40s. There were various projects going on to build, to realize general-purpose computers in the late '40s, but if you've heard about EDVAC or ENIAC, which were the projects John von Neumann were involved in, those would be two examples. So this is rewinding ten years before that, before anyone was even trying to build computers.
▶︎ 3:46 And in fact, at this time, in 1936, the word existed, the word "computer" existed, but what it actually referred to was a job description, like a profession that humans would have. You can imagine that even in the '30s, there was plenty of need for systematic calculations. Maybe you're doing astronomy, maybe you're in the military, maybe you're planning a business. There were lots of reasons you needed large-scale calculations, and so human beings in the '30s were employed to do that, and they were referred to as computers. So that's what that word meant back in the 1930s. So that's the first thing that's wild, the invention in some sense of computer science as an academic discipline, a scientific discipline ten years before we actually had computers.
▶︎ 4:29 The second thing that's wild is Turing basically did this as a byproduct of trying and succeeding to resolve a mathematical problem, which was big among mathematicians. That was this Entscheidungsproblem that I mentioned. But to anyone else, completely esoteric. So in pursuit of resolving this mathematical question, as a byproduct Turing's paper really gave birth to the discipline of computer science.
▶︎ 4:58 So the mathematical problem in question is the one referred to in the title, Entscheidungsproblem. Literally that translates to decision problem, which doesn't, I don't know, that shouldn't really mean anything to you. So you're like, "Okay, what's that, and why would anybody care?" So let me actually talk a little bit about that mathematical backstory before we get into what Turing did in this paper.
▶︎ 5:20 A lot of the backstory has to do with a famous German mathematician in the late 19th century, early 20th century, named David Hilbert. Hilbert's famous for a number of things. One thing he did is he keenly understood the role of open problems in mathematics, and if you don't know any professional mathematicians, I can't understate how much the field of mathematics revolves around big open problems. For example, Hilbert, back in 1900, gave a keynote address at the International Congress of Mathematicians, 1900. This was one of the first ICMs. It was in Paris.
▶︎ 5:58 And in his talk, he presented a list of unresolved mathematical problems, problems where we didn't know whether it was true or false, and if it was true, we didn't know how to prove it. I think there were 23. Anyways, this list of open problems, and he issued it as a challenge to the field. And again, open problems have just been a tremendous organizing force for mathematical disciplines, giving everybody a yardstick by which you can measure progress, by which you can assess when there's been a big breakthrough, which is when one of these big open problems gets resolved. So even if people conjecture mathematical statements and they wind up being false, it doesn't matter. It still leads to an amazing amount of scientific progress.
▶︎ 6:42 We'll return to this in a different episode, but in homage to Hilbert's 1900 list of open problems, in 2000, the Clay Institute issued seven millennium problems, which were again meant to inspire the full field of mathematics, to rally around trying to solve these deep, open questions. One of those is what's known as the P versus NP question, which we'll return to in the fourth episode.
▶︎ 7:09 In any case, some of these problems on Hilbert's list in 1900 concerned, in some sense, establishing that we're doing mathematics the right way. That the way we try to prove statements being true is in fact what he would call complete, meaning that whenever you have a mathematical assertion which is in fact true, there should be an argument, a proof, a finite sequence of logical steps, that establishes it. So whenever you have a true statement, Hilbert was speculating that there should be a proof that demonstrates that truth. And then furthermore, and this is the decision problem, it would be nice if there was a mechanical method, if there was an automated way, in some sense, of arriving at these proofs of true statements.
▶︎ 7:58 So that was part of the Hilbert program, which you saw seeds of in that 1900 address. He continued to develop it over the early 20th century. He wrote a book in 1928, Principles of Mathematical Logic, where he really at that point had very crisp conjectures about what should be true about mathematics as we know it.
▶︎ 8:17 And so Turing's paper is part of this context. Turing's paper was eight years after that book was published, for example. Now, in between Hilbert and Turing is another name you might have heard of, Kurt Gödel, who was a famous logician. And Gödel in 1931 proved something known as Gödel's incompleteness theorem, and so this was a big result. This result basically said that the first thing Hilbert conjectured was wrong. That actually it's not true, that the way we write down mathematics, the way we write down proofs, is sufficient to establish all true statements.
▶︎ 8:54 There are statements which we regard as true, but elude the way we prove them. In some sense, the number of true statements outnumbers the number of proofs that we can come up with. So this is known as saying that mathematics is not complete. There are true statements for which you will not have a proof. That was a really big deal. So that was in 1931, basically shattered a lot of Hilbert's vision for what he was hoping would be true.
▶︎ 9:20 And I should say, Gödel's incompleteness theorem, I don't have time to get into it too much. That would be a great different episode, to talk about its implications not just in mathematics, but it resonated much more broadly. For example in philosophy, most famously maybe the Lucas-Penrose interpretation, which they interpreted as saying, there are things about humans that cannot be simulated by computers. Of course, other people would debate that point. That would be a great debate, a little bit of outside of our scope. So what I want to do is just move from 1931, and Gödel shattering part of Hilbert's program, and now go five years further to 1936.
▶︎ 9:55 So what was left for Turing to do after Gödel's incompleteness theorem? Well, in mathematics you do this. You're hoping something's true, someone shows you it's not true. You're like, what would be the next best thing? What's the coolest thing that could be true, given what we know to this point? So there's gonna be statements that are true, where we can prove them. One plus one equals two. Easy enough. There's gonna be other statements, ones that Gödel exhibited, that are true but which we're not gonna be able to prove.
▶︎ 10:26 So what about the automated part of Hilbert's program, that there should be a mechanical way of generating proofs of true statements? Well, now the coolest thing that could be true is that whenever there is a proof, we know that's not gonna be the case for all true statements, but whenever you have a provable true statement, in those cases we would like an automated way of arriving at that proof. And that was the decision problem that Turing addressed.
▶︎ 10:53 Gödel's result did not rule out the possibility that in the event that a statement is true, you could, in a mechanical way, generate a proof of it, and this is exactly what Turing showed is also not the case, in his famous 1936 paper. So what would it mean to disprove the decision problem? I guess what you have to show is you have to show that there are true statements for which there's a proof, for which that proof eludes any mechanical method you might try to use to find it. But that's a little tricky, right? Because what do you mean by any mechanical method? That is not a mathematically well-defined concept, or at least it wasn't before Turing's paper.
▶︎ 11:44 To even make sense of this question, to make sense of what it would mean to show the decision problem is false, one has to necessarily commit to a mathematical formalization of what mechanical procedures, in our context we would say computers, a mathematical model of what computers can do. In order to show limitations on computation, in order to show that there are things that mechanical procedures or computers cannot do, you must first formalize what it is that they can do. This brings us to the first big reason why Turing's 1936 paper is so important. His mathematical formalization of what mechanical procedures, or what we would call computers, can do.
▶︎ 12:32 How did he formalize that? Well, if you've ever heard of a Turing machine, that's where, this is where Turing machines enter the story. I want to tell you a little bit about what a Turing machine is, give you a cartoon picture you can have in your mind. And we've got this beautiful whiteboard to work with, so let's put it to use.
▶︎ 12:54 By all accounts, when Turing came up with the idea of a Turing machine, he was really inspired by the human computers we were talking about earlier, literally just people like you and me with a big scratch pad and a pen carrying out lots of calculations. So he literally said, "Let's think about a big roll of paper, as long as you want, and just roll it out on the ground, from here, extending as far as you like out to the right." That's part of how we think of a Turing machine, a long roll of paper. And there's different locations on this paper that you could be using potentially, that you could be working with. Maybe there's some numbers in different parts of this piece of paper, for example. And maybe there's other arithmetic symbols, whatever.
▶︎ 13:45 And then there's an actual person who is doing calculations somewhere on this piece of paper. Maybe here's your human being working on this part of the piece of paper. Maybe potentially says, "You know what? I just did a new intermediate calculation. I'm going to change the one to a four, and now I want to see what's going on. I want to remember what I wrote on the piece of paper a little bit further down on the roll." That basically is a Turing machine.
▶︎ 14:17 A program, if you like, is specified by a small list of rules. As a person, when you're looking and you see a number, you might replace that with some new number, and there's a set of rules that specify what you should overwrite that old number with. For example, if you're carrying out addition, that's going to be one set of rules. If you're carrying out multiplication, that's going to be a different set of rules. It's going to be different calculations that you carry out on this long piece of paper.
▶︎ 14:47 And to say one step of a Turing machine, that is exactly what we saw here. That is, you are looking at some part in this working paper that you've got. You're looking at the value at the piece of paper where you're at. If you want, you can use your set of rules to figure out some new number to overwrite with, and then you can, if you want, move to the right or to the left along this piece of paper. All the while, if you want, you can have some bounded amount of memory to keep track of some of the things that you've seen and done in the past. And that honestly, really, that is a Turing machine.
▶︎ 15:27 Now, this Turing machine might strike you as pretty quaint, especially when you think about, I don't know, maybe you've got a fancy new MacBook Pro on your desk or something like that. You're like, "Eh, seems like this laptop is a little bit more useful, a little bit more powerful than a Turing machine." And obviously there's senses in which that's true, but in a much deeper sense, in a much more fundamental sense, in fact, the MacBook Pro that you're using is not more powerful than these Turing machines. In fact, we believe that Turing machines are as powerful as any reasonable model of computation, including just very direct models of the computers that we use, even today. So that belief that Turing machines capture computation in its full generality, that belief is something known as the Church-Turing thesis. We will return to that at the end of this episode.
▶︎ 16:26 Now at first this might seem crazy. You're probably like, "Wait a minute. You're telling me that cartoon is as powerful as my new laptop, shiny new laptop. That's what you're trying to say." Let me just mention a couple things to maybe make the gap seem a little bit smaller than it might initially appear. So the first thing to notice is that you really can program a Turing machine. Remember, I said that the human computer, they look at this value on this piece of paper and decide a new value to write, move to the left, move to the right. That's one step.
▶︎ 17:00 All of those decisions, what new number to write, whether to move left or right, all of that is defined by the set of rules. Like I said, for addition, you would use one set of rules. For multiplying two things, you would use a different set of rules. And the rules can be whatever you want. They can be super complicated. You could have a million rules specifying all kind of crazy things to do in different kinds of circumstances.
▶︎ 17:26 So there's a literally infinite number of possible programs you could run on a Turing machine, different rules that this calculator could use to update all of these values on the piece of paper. So that's the first thing to notice. It is not just one type of calculation. It is whatever calculations you can write down rules to do. That's the first thing.
▶︎ 17:47 The second thing, and again, this may or may not resonate with you depending on if you've seen examples, but even if you fix the program, even if you fix the set of rules, honestly even sometimes for very short lists of rules, if you iterate some very simple rules over and over and over and over and over again, you can have remarkably complex phenomena emerge. If you've ever seen John Conway's Game of Life, that would be a great example. Where very simple rules can lead to, and they're very visual, lead to extremely complex behaviors.
▶︎ 18:22 Honestly, if you think about it, even biological evolution, one would regard as complexity, remarkable complexity, mainly us, arriving from the application of simple rules over and over and over again for millions of years. And it gets even crazier. So this is outside our scope, but if this intrigues you, complexity arising from seemingly tiny simple programs, have a look up of the busy beaver function, which actually is defined in terms of Turing machines and shows just how crazy the behavior of Turing machines can be, even for these very simple families of rules.
▶︎ 19:00 So those are two reasons why, maybe you don't yet believe that Turing machines are as powerful as your laptop in some deep fundamental sense. But hopefully you'll concede and say, "Okay, I guess, yeah, they're gonna be able to do stuff, at least in principle." You could program them in all these different ways. Even simple programs can have complex behaviors.
▶︎ 19:18 And so then you might start getting concerned in a different direction. You might be saying, "Well, but wait a minute. Given that there's so many different things a Turing machine can do, so many different programs you can run, and the programs can generate such complex behavior, how would you ever establish limitations on what they can do? How would you say that no Turing machine, no program, no matter how clever, no matter how sophisticated, could carry out some sort of task of interest? That seems like a very ambitious thing to say. It seems like Turing machines could do a lot of stuff. How would you ever argue that there are things that they fundamentally cannot do?"
▶︎ 19:57 And that is the second reason why Turing's paper from 1936 is so important. Not only did he propose this mathematical formalization of what it is mechanical procedures, or computers, as we would say, can do, he showed that there are problems known as undecidable problems which computers will never be able to solve. And not just weird, artificial problems we'd never care about. Problems we actually really would, we really would ideally want to solve are fundamentally unsolvable by computers. And not just today's computers. The computers of tomorrow, the computers of a thousand years from now, the computers of a million years from now. The problems that fundamentally elude computation in its full generality.
▶︎ 20:41 And this, I find this kind of poignant, honestly, because as a computer scientist, because you literally go back to the absolute day one of our discipline, of computer science, in some sense. And literally from day one, we have known disappointment. We have known that, for all of the amazing things computers can do, there are limits. That was established at the exact same time as the concept was formalized. And so that's part of the legacy of the discipline of computer science. All right, so next, another
▶︎ 21:14 One thing you might wonder is, well, as you think about this a little bit more, you're like, "Should we really be that surprised actually, that there are problems that elude computation by Turing machines?" I talked about how there's lots of Turing machines. This set of rules can be any set of rules. Finite, but as long as you want. So there's a ton of programs out there. But then you might say, "But it also seems like there's a ton of tasks we might ask computers to carry out." There's just a zillion problems that if you wanted, you could try to get Turing machines to solve. So maybe even the number of problems out there in the world outnumbers the number of Turing machines, or the number of programs in some sense. So just by being outnumbered, just by that counting argument, perhaps there are these unsolvable problems.
▶︎ 21:59 But Turing's paper actually proves something much more interesting than just the existence of unsolvable problems, what he calls undecidable problems. But again, even very practically well motivated problems we would love to solve, like there would be useful technology that you could build a company around, even problems of that nature can be unsolvable by computers. And so to give you an example, you can imagine you might think about the problem of finding bugs in programs. Bugs mean errors in programs. You probably knew that. If you don't know why they're called that, it's because those same computer systems in the late 1940s I was talking about, they were filled with vacuum tubes and flies would get into the vacuum tubes and then the thing would break and they'd have to resurrect the computer because literally a bug got in the vacuum tube. So that's why we still call errors in programs bugs to this day.
▶︎ 22:48 Anyways, you want computer code to be correct. You don't want someone to hack into your laptop because there's a bug in the operating system. Those of you that have tried to program yourself know it's very easy to make mistakes. You're very happy to have help in the form of automated tools to point out errors in your programs. And of course, speaking now, speaking in 2026, a lot of code is being generated by AI, and of course we would like tools to verify the correctness of this automatically generated code. Super, super practical problem.
▶︎ 23:23 Now, here's a very, very special case of trying to find a bug in a program, something called the halting problem. I give you a computer program. I give you some code. Think of it as, I don't know, 200 lines of Python or any other programming language you might be familiar with. So I give you this, really short, just like a few pages, few pages of code. And I ask you, "If you ran this program, would it complete? Would it halt? Would it stop? Or would it run forever?" For example, because it gets caught in an infinite loop. I just want to know which of those two things is the case. And so that's the halting problem. I give you a piece of code and I just want from you a yes or a no. Will it halt or will it not halt?
▶︎ 24:08 And your first thought might be, "Easy. Give me the program. I'll run it. I'll see what happens." And if it halts, great. You say, "Yeah, the program halts. I ran it. I saw it for my own, with my own two eyes." Fine. But what if you run the program and it's 10 minutes later and it hasn't halted, it's still running. You're like, "Okay. Let's give it a little more time. Maybe run it overnight." And you wake up the next morning and it's still running. You're like, "All right, maybe it's in an infinite loop. But maybe it's actually doing a pretty hard computation." So maybe you wait a year and it's still running. And at that point, you're like, "It's gotta be in an infinite loop. What else could possibly be going on?"
▶︎ 24:51 But remember, what did we say? We said even very short programs can exhibit tremendously complex behavior. And again, the computation of these busy beaver functions that I mentioned earlier are the classic, classic example of very short computations running for an obscene number of steps. So the bottom line is that even if you've run it for a year and it hasn't halted, you have no idea whether it's going to halt tomorrow or not. So that shows that the obvious way of trying to address the halting problem, by mere simulation of the program, is not going to work. Because you are never sure that it's in an infinite loop. You're never sure that it's not going to halt tomorrow.
▶︎ 25:33 But the question is, that's the most naive, obvious way to try to determine if a program will halt or not. What about some more clever methods, some more clever shortcuts? And we'll see a lot of clever algorithmic shortcuts in the next episode. So you might ask for one with a halting problem. "Look, it's 200 lines of code. Stare at it, think about it, analyze it, just tell me the answer." That's the halting problem.
▶︎ 25:57 The halting problem, Turing showed, undecidable. There's literally no automated procedure that will take your 200 lines of code and always correctly tell you whether or not it will halt. And this is not a limitation of our intelligence. This is not a limitation of 2026 technology. A thousand years from now, it will remain true. This is part of the nature of the universe. It will remain true that there is no automated procedure for solving the halting problem.
▶︎ 26:30 And to see the connection between this undecidability of the halting problem and the decision problem that Hilbert asked about. If you're trying to, in an automated way, try to come up with a proof for some true statement, one thing you can do is, you can, in some sense, just try all proofs. So you try all proofs that have only, that are only one line long. Then you try all proofs that are only two lines long, then all proofs that are only three lines long, and so on. But it's the same kind of problem. It's like, once, if for example, you successfully figured out no proof with at most 10,000 lines is a proof of this statement, you cannot directly conclude that this statement is unprovable, because there might be a proof with just one more line, 10,001 lines, that establishes that statement.
▶︎ 27:20 So in the same spirit that you cannot solve the halting problem through mere simulation, and more generally by any other method, same too with the decision problem. You cannot determine provability just by trying longer and longer proofs, nor, as follows from Turing's work, nor can you do it via any other method.
▶︎ 27:39 Now mind you, there will be mathematical statements where we'll be able to find the proof for it. If you take a math class, everything you learn is proofs of true statements. Same thing with the halting problem. There will be programs where you're like, "Yeah, obviously this halts. It's like a straight-line program with no loops, no problem." There'll be other programs where you're like, "Oh, it immediately goes into an infinite loop. Obviously it doesn't halt." But the point is, there is no general automated procedure which is guaranteed to tell you, given your favorite piece of code, whether it halts or not. Similarly, there is no generic automated procedure that takes as input some mathematical statement and tells you whether it's provable or not.
▶︎ 28:22 So Turing's development of undecidability, the idea that there are natural problems that computers will never be able to solve, that is so important that I wanna tell you about, I wanna spend some time on the key ideas.
▶︎ 28:35 And I think there's tremendous conceptual beauty in his arguments. And so I want to try to have that come out in the following discussion. I would break it down into three big ideas, in Turing's argument, about why the halting problem in particular is unsolvable.
▶︎ 28:50 The first step concerns the concepts of universality and simulation. By universality, I mean that one of the first observations Turing makes in his paper is that there is, in effect, one Turing machine to rule them all. Thus far, we've been thinking about Turing machines tasked with carrying out some rather specific task, tasked with adding two numbers, tasked with multiplying two numbers. But the observation is actually, Turing machines are powerful enough to simulate other Turing machines.
▶︎ 29:27 To give you a sense of what this means, let me just augment what I've got on the board a little bit. Again, thus far, we've been thinking about Turing machines, like maybe you're given two numbers, like 5678 and 1234, and you're supposed to add them, you're supposed to multiply them. But now imagine, actually, let's suppose there's some more stuff. Let's suppose, actually, that in addition to, for example, two numbers, you are given, so it's written down on this piece of paper. This is part of the input, if you like. You are given a description of a Turing machine, call it M.
▶︎ 30:09 And then this is going to be a universal Turing machine, call it M sub U. So the universal Turing machine is expecting to be told a description of a program, a description of some other Turing machine in the form of the rules that you're supposed to follow in the Turing machine M. And then what the universal Turing machine can do is simulate this Turing machine M on whatever the input is in this case.
▶︎ 30:39 So for example, suppose you're running the universal Turing machine, and you're here and you're trying to figure out, there's a one here. Do I overwrite it? If I overwrite it, what value do I overwrite it with? Do I move to the left? Do I move to the right? In the universal Turing machine, you ask yourself, well, what would the Turing machine M do? So you go over and you read the rules of the Turing machine M that you were provided with. And based on the rules, you go and modify the numbers accordingly. So that's what I mean by one Turing machine M sub U simulating another. Given a description of some Turing machine, the universal Turing machine can simulate its computation.
▶︎ 31:21 Now I know this might be hard to grok or just seem like super abstract, but honestly, just from your day-to-day use with computers, you're totally familiar with this idea. So this universal Turing machine, this is basically the operating system of your computer. So if you use a Mac, it would be macOS, or maybe you use a Windows machine, maybe some other operating system. But the operating system is somehow the master program which controls and executes all of the other programs you have in mind. So if you're running a spreadsheet, if you're running a PDF reader, whatever, those instructions are carried out or managed by your computer's operating system.
▶︎ 31:59 So think of the operating system as the universal Turing machine. Just like your operating system can run any program it wants, so too this universal Turing machine can run any Turing machine that it wants. So that's what I mean by universality. There could be one Turing machine to rule them all, one Turing machine capable of simulating any other thing you could possibly do with a Turing machine.
▶︎ 32:25 Given that, and I should say, I use the phrase, you hear the phrase general purpose. Computers are general purpose. You hear that a lot. And this is really what that means. And honestly, again, even this is 1936, 10 years before computers existed, this is one of the most fundamental concepts in computer architecture, which is programs as data. So you can have value stored in the memory of your computer. It might represent something like your bank balance, a number that has meaning, or it might be a bunch of zeros and ones which represent instructions, which represent code.
▶︎ 33:01 And these are treated identically in modern computers. And that idea is already here in the universal Turing machine. Stuff on this piece of paper, maybe they represent things like actual numbers you might care about, maybe it represents code to be run. Code as data, already there in 1936 in Turing's universal Turing machine.
▶︎ 33:24 This is really something that's special, honestly, about computer science. Forgive me, I'm biased, I'm a computer scientist. I've devoted my life to this discipline. But if you'll allow me to just cheerlead a little bit, because we've had computers our whole lives, so we just take this for granted, their general purpose in nature, but it's really amazing. So you do not buy a different computer to browse the web and then another separate computer to read PDF files and then another computer to do spreadsheet work. You have one computer and it does all of those things.
▶︎ 33:59 And I know you're probably thinking, well, obviously that's how it works. What do you mean? But think about kitchen appliances. We have a small kitchen, and yet somehow there's very limited real estate. We use some of it for an oven and some of it for a toaster oven. These two things do the same thing. They both warm up food. It's just one is better for bagels and one is better for steaks. So we use up two different parts of our kitchen with this almost identical functionality. You are never buying two different computers for any two different computing tasks. The one computer does it all.
▶︎ 34:38 And this is not unrelated to why computer science is in fact an academic discipline and toaster science is not. So toasters, that is the narrow application of general purpose ideas from physics and engineering. Computer science is about really computation. And again, computation's something that literally transcends technology. It's literally part of the mysteries of the universe.
▶︎ 35:02 Now, it took a while, honestly, for this to become mainstream opinion that computer science was actually a legitimate academic discipline. Like I said, people were building computers already in the '40s to carry out various tasks. Mid-'60s is when you saw the first academic departments in computer science. But even in the '70s, Harry Lewis, who's a professor at Harvard who later taught Bill Gates and Mark Zuckerberg and people like that, was having a heck of a time convincing his colleagues that computer science made sense as a discipline, even as late as the 1970s.
▶︎ 35:36 So the quote that he said a lot of his colleagues would make in the 1970s was, "We don't have a department of microscope science for biologists. We don't have a department of telescope science for the astronomers, so why should we have a department of computer science?" So already, even in the 1970s, it was not widely recognized as a scientific discipline. Happy to say, in the 2020s, it definitely is. So that's the first part of Turing's argument about the undecidability of the halting problem.
▶︎ 36:03 Universality and simulation, the idea of this universal Turing machine that can simulate any other Turing machine. Now the second part of the argument is the deft application of a proof technique known as diagonalization. This is a technique that I don't know whether to say it was invented or whether to say it was discovered, but either way, George Cantor, 1891, Cantor was interested in proving that there's more real numbers than integers.
▶︎ 36:32 If you've never seen this stuff before, you might think, what does that even mean? There's an infinite number of integers, right? One, two, three, as big as you want. And there's an infinite number of real numbers. The integers in particular are real numbers. So they're both infinite. What do you mean there's more real numbers than integers? But there are, in a meaningful sense. So there are different levels of infinity, if you like. And the set of real numbers is a higher level of infinity, infinite cardinality, than the integers.
▶︎ 37:05 Very intuitively one way to think about it is, if you remember, real numbers have a decimal expansion. Like pi, 3.14159265358979 dot dot dot. It goes out forever. Infinite number of digits. Whereas any integer, any sort of natural number has a finite number of digits. So heuristically, this is semi-accurate. Real numbers, by virtue of having an infinite number of digits, there's fundamentally more of them than there are integers.
▶︎ 37:32 There's a few ways to prove that. One of the ways which Cantor came up with is known as diagonalization. I don't know if you think of mathematics as having controversies. But this was definitely a controversy, in the sense that Cantor's diagonalization proof was flat-out rejected by many other mathematicians at the time. It was this combination of a proof by contradiction using infinite objects, which just struck some mathematicians as quite dodgy, I would say. So there's this debate over whether Cantor's proof was legitimate for establishing the separation between the integers and the reals.
▶︎ 38:08 The same David Hilbert we talked about earlier actually was one of the fans of Cantor's argument. Thought diagonalization was actually really cool. Famously, Hilbert said, this was in '26, "No one shall expel us from the paradise that Cantor has created." And in fact, one of the goals of Hilbert's program that I mentioned of formalizing the idea that we're doing mathematics in the right way, one thing he was hoping would come out of that would be some kind of formal justification of the legitimacy of Cantor's diagonalization argument. And that then made it particularly ironic when diagonalization was the main proof technique in taking down Hilbert's program, as practiced both by Gödel, who we mentioned earlier, and by Turing.
▶︎ 38:56 Gödel, as we talked about, proved the incompleteness theorem. There are true statements that are not provable. Gödel proved this using diagonalization. So the very technique Hilbert wanted to justify showed the incompleteness of mathematics, of the way that we were doing mathematics. And again, it turns out that self-referentiality tends to unlock the power of diagonalization.
▶︎ 39:27 So the key thing that Gödel showed, Gödel showed that you could take statements about the integers, statements in arithmetic, and encode them themselves as integers, give them numbers in a sense. So you could have numbers standing both as what we think of them as, as a number, but also as an encoding of an assertion about numbers. So that's what I mean by self-referentiality. And so Gödel combined that with diagonalization to show that, in fact, there are statements that are true but not provable.
▶︎ 40:02 Now, Turing came up with this self-referentiality through the universal Turing machine, a Turing machine that can run Turing machines, the way Gödel had integers that encode statements about integers. And so Turing recognized the pattern and he said, "Aha." Just in the way diagonalization served Gödel for taking down the completeness conjecture, it also served Turing in taking down the decision problem. So through diagonalization, Turing showed that there exists an explicit computational problem. It's a peculiar problem, not that natural. I'm not gonna tell you what it is, but whatever. An explicit computational problem which was provably undecidable, for which there was no mechanical way of solving that problem.
▶︎ 40:47 So that brings me to the third and final big conceptual idea in Turing's argument, which is to show that not only this one explicit peculiar problem he identified through diagonalization. It's not just that that's undecidable. So are natural problems that we would really want to solve. And in particular, the halting problem is undecidable. So the third step of the argument is to transfer the undecidability already established for one problem in the second step to transfer that undecidability to the target problem, the problem he really cared about, which was the halting problem.
▶︎ 41:21 And so this transfer, this is an idea known as a reduction. And reductions are one of the most central concepts in the foundations of computer science. We will see them again in a couple episodes when we talk about NP-completeness. But for today, the role of a reduction is going to be to transfer unsolvability, undecidability from one problem to another.
▶︎ 41:45 So what's a reduction? Honestly, we're all super familiar with reductions from day-to-day life. What it means in the context of computation is basically the same. Let me give you an example. So maybe you're at work. You go out to happy hour with your colleagues. And you go to some bar you hadn't been to before, whatever, half a mile away, something like that. And happy hour wraps up. You gotta get home. And you're like, "Huh. How am I gonna get home?"
▶︎ 42:11 And now, I know in 2026, you ask your phone. It tells you all the steps you need to get home. So suppose it's the 1980s. And it's the same story. So the 1980s, you don't have any sort of automated way of generating directions for you. And you went from work to happy hour. You gotta get home. Well, you could say, "Well, you know what? I know how to get home from work. I do that every day." So I'm just gonna reduce my task of getting home from happy hour to getting home from work. And I'm gonna do that by walking back to work from happy hour. I'm just gonna retrace my steps I used to get to the bar, and then I'm just gonna follow my usual routine to get home from work.
▶︎ 42:50 So what did you do? There was a reduction. The reduction was walking back from happy hour to work. So the problem you needed to solve was getting home from happy hour, the problem you already knew how to solve was how to get home from work, and the reduction provides the bridge in between the two.
▶︎ 43:04 Or for another example, maybe you're like a Microsoft Excel wizard and you can do all kinds of amazing things with an Excel spreadsheet. But then someone gives you a bunch of data in Google Sheets, say, and you're like, "I don't really know how to do much stuff with Google Sheets." But there's a reduction. You reduce it to a problem you already know how to solve. You export your Google Sheets data into Excel, and now you do your usual thing. So the problem you needed to solve was fancy analysis of data in Google Sheets. The problem you knew how to solve was doing fancy analysis of data in Excel. The reduction was just the exporting of the data from Sheets to Excel. And so that's what a reduction means. It's just a way of solving one problem by doing a little bit of work to reduce it to a problem that you already know how to solve.
▶︎ 43:52 So let me give you a visual. So we're thinking of there being two problems, problem A and problem B, and we're thinking about there being a reduction. And again, the reduction just means that if you know how to solve B, then because of the reduction, you're also going to know how to solve A. So in our examples, problem B would be, for example, doing magic in Excel. That's what you already know how to solve. The reduction is just exporting sheets into Excel so then you know how to do magic, spreadsheet magic with Google Sheets. So for the going after drinks example, you know how to get home from work, and because you know how to walk back, retrace your steps from happy hour to work, you know how to get home from happy hour.
▶︎ 44:46 So that's the usual way that one thinks about reductions. You already know how to solve one problem, problem B, and a reduction that enables you to solve other problems as well, problem A. But the way we're gonna use reductions here is actually gonna be, it's logically equivalent, it's just gonna be the contrapositive, but it's somehow a much, most people find this much less intuitive, a little bit mind-bending even. Which is that suppose you actually cannot solve problem A. And again, we're talking about problems that can't be solved by computers. Undecidable problems. Suppose a problem cannot be solved, like problem A. Well, then if you think about it, if you have a reduction, that means you're not gonna solve problem B either. Because if you could solve problem B, well then using the reduction, you can solve problem A as well. But we can't solve problem A.
▶︎ 45:37 So reductions have the effect of spreading undecidability from one problem to another. And it gets spread in the exact same direction. So if problem A reduces to problem B, then in fact, and A is undecidable, unsolvable, then so is problem B. So spreads undecidability.
▶︎ 46:08 Let me say the argument one more time. I know it's simple, but again, most of us need a couple repetitions to really rock this. The claim is that if you have a problem which is unsolvable, you don't know how to solve, and you have a reduction to some other problem, well then the latter problem must be unsolvable as well. Why? If you could solve problem B, then because you have a reduction, you would know how to solve problem A as well. If you can't solve problem A and it reduces to problem B, you can't solve problem B either.
▶︎ 46:38 And so now, we see what Turing's last step is going to look like. What I said is that in the second step of Turing's argument, diagonalization gives you an explicit, if somewhat peculiar problem, which is provably unsolvable. So for Turing, problem A is gonna be the peculiar undecidable problem from second step, from step number two of his argument. And problem B for Turing is gonna be the halting problem. And then as long as you can exhibit a reduction from the peculiar problem to the halting problem, boom, you're done. You've already showed that the problem on the left is undecidable. Reductions spread undecidability, so that would spread undecidability to the halting problem.
▶︎ 47:37 So that is the third step of Turing's argument, that indeed there is a reduction, it's not that hard, I'm not gonna get into the details here, but there's a reasonably straightforward reduction from the peculiar undecidable problem to the halting problem, again, spreading undecidability from the former to the latter. So those are the details I wanted to tell you about Turing's argument, that the halting problem is undecidable.
▶︎ 48:00 I hope the brilliance and the creativity of his argument comes out from this discussion. Now that we've covered that, now I want to move on to how do we interpret Turing's result of the undecidability of the halting problem. I've been speaking about the result with an interpretation in mind, which is that by virtue of being unsolvable by Turing machines, which is the mathematical statement that Turing proved, I'm interpreting that as being unsolvable by computers. And you might feel like there's a gap missing there. The worry would be that, well, are we so sure that the Turing machine model, this quaint picture of this human with a long roll of paper and the pen. Are we so sure that the model of Turing machines captures everything that computation in its full glory might be able to do?
▶︎ 49:00 This really says, how do we feel about Turing's definition of the Turing machine? Do we share his belief that Turing machines in fact capture everything that is possible through computation in any form? Definitions, like Turing's definition of a Turing machine, they play an incredibly important role in mathematics. The spotlight usually goes to the big theorems, Fermat's Last Theorem, that kind of thing. The definitions, those are often below the fold. But they are absolutely crucial to everything that happens in mathematics.
▶︎ 49:35 As such, when you see a definition, a mathematical definition, you should poke it, you should prod it, you should criticize it, you should question it. You can ask, is it too strong? Does it include too many things? Does it include too few things? Does it capture the real-life concept it's attempting to formalize? All of those are good questions.
▶︎ 49:52 Before we do that with Turing's definition of a Turing machine, I just want to stop and say, it takes a lot of courage, actually, to write down a mathematical definition like this. To take some seemingly messy real-world concept like automatable, or like solvable with a mechanical process, and to actually try to translate that into cold, rigid math. That is difficult to do. Anytime someone makes an attempt, we should applaud it, and then we should immediately proceed to interrogating the definition. But just to be clear. This will be even more obvious when we talk about P and NP completeness in a couple episodes. Just very courageous attempts to take messy real-world concepts, turn them into mathematics that we can then build theories around.
▶︎ 50:39 And in general, with a definition, one of the things you worry about is that it's too broad. That things are covered under the definition that you think really should be excluded. And we'll worry about that, for example, in a couple episodes when we talk about, maybe we should actually zoom in specifically on Turing machines that can solve problems efficiently, quickly, not just in principle. We'll worry about that later. At the moment, we're more concerned about Turing's definition being overly narrow.
▶︎ 51:07 What we're worried about is that the math tells us, Turing machines can't solve the halting problem. But can we really leap to the conclusion that our modern MacBook Pros also cannot solve the halting problem? Maybe there's more powerful versions of computation not covered by Turing's quaint Turing machines. The widespread belief among computer scientists is that in fact, Turing was right. That Turing machines really do capture any reasonable model of computation. So if Turing machines can't solve some problem, neither can any other technology that will ever be invented either.
▶︎ 51:45 Now, but how would you build evidence for that mathematically? The way you do it is, actually again by simulation. We talked about simulation once. That was in the first part of Turing's argument about undecidability. We talked about the universal Turing machine simulating other Turing machines. A good way to argue that the Turing machine's as powerful as anything else is enumerate all the other notions of computation you can think of, and then show one by one, for any competing model of computation, show that whatever that model can do, Turing machines can do also.
▶︎ 52:24 How do you show that? You show that by simulation. You give me an example of a computation in your model, I'll give you back a Turing machine that does exactly the same computation. And if you can carry out that simulation for model after model after model that anybody can think of, that happens for long enough, you start wondering, wow, maybe actually there isn't anything out there beyond Turing machines. And that's the state of the art.
▶︎ 52:49 Any other reasonable model of computation that people have dreamed up, whether it's, for example, modern computers and their RAM-based architecture, doesn't matter. Any other model of computation people have dreamed up, Turing machines have always been powerful enough to simulate them. Any computation they can do, Turing machines can do as well. So you might be wondering about what these other models of computation other than Turing machines might be. Another thing you might be wondering about would be, who is Church?
▶︎ 53:17 Why is it called the Church-Turing thesis and not just Turing's thesis? And there's related answers to those questions. It turns out, there was a logician, Alonzo Church, at that time at Princeton, who, for the exact same reasons, because of Hilbert's 1928 book with all these open problems, was also motivated by the exact same decision problem, and also set out to disprove it. And in fact, Church actually beat Turing to the punch by a few months. It was nearly independent, but Church was a few months earlier.
▶︎ 53:50 Now, Turing, after he had completed all his work, only then did he find out about Church's work. But he was encouraged to publish his paper anyways, which he did, fortunately. Because Turing's methodology was very different than Church's, and in some ways, more direct. And even then, it seemed like the formalism he came up with might have many, many other applications. And of course, now we know for a fact that indeed it does.
▶︎ 54:14 So Church, he didn't invent Turing machines, but he had to invent some other model of computation, which he called the lambda calculus, which also has lots of applications. It less obviously corresponds to mechanistic processes and computers as we know them. But in the appendix of Turing's 1936 paper, he includes a proof of simulation. So again, lambda calculus is another model for expressing computations, and it turns out that Turing machines can express any computation expressible in the lambda calculus, and indeed vice versa. The converse is also true.
▶︎ 54:51 And we now know that this exact same thing is true for lots of different ways of expressing computation. There's even a phrase, Turing-complete, which means a method of expressing computations which is as general as Turing machines and therefore everything else that we know about.
▶︎ 55:07 So let me just leave you with one final story given that we're talking about Church. And I gotta tell you, this is very lazy storytelling. Telling stories about bizarre things that mathematicians have done is like shooting fish in a barrel. There's just a million such stories. But there's one about Church which I first read as a grad student. We're talking 25 plus years ago. And for whatever reason, this one just stuck with me so I can't help but tell you the story as well.
▶︎ 55:44 I learned it from the recounting of another famous mathematician, Gian-Carlo Rota, who did a lot of important work, for example, in combinatorics, and was a student at Princeton doing his PhD at that time. So one comment Church says is that, "It cannot be a complete coincidence..." Oh sorry, this is Rota speaking now. "It cannot be a complete coincidence that several outstanding logicians of the 20th century found shelter in asylums at some time in their lives. Cantor, Zermelo, Godel, Peano, and Post are some." And indeed, you could have an entire episode just about the different ways that different logicians lost their minds. It's a really striking recurrence, I'd say, in that part of mathematics.
▶︎ 56:28 So Rota goes on to say, "Alonzo Church was one of the saner among them, though in some ways his behavior must be classified as strange even by mathematicians' standards." And he talks about taking the graduate logic course from Church at Princeton, and this is the part that I just never forgot when I read it 25 years ago. "Every lecture began with a 10-minute ceremony of erasing the blackboard until it was completely spotless. This ritual could not be disposed of. Often, it required water, soap, and a brush, and was followed by another 10 minutes of total silence while the blackboard was drying."
▶︎ 57:19 The students, out of exasperation, would get to class 15 minutes before Church, later in the semester, to do all that work for him, preprocessing. Let's make sure the board is spotless before Church gets here. Didn't matter. Didn't matter. Church would still take the 10 minutes and erase the whole blackboard with soap and water every single time. And I don't have time to tell you the whole Rota article. But Rota writes all this, I will say, with a fondness for Church, just to be clear, and for the imprint on Rota's thinking that Church left him in that class. So strange, yes, but all sort of part of the mathematical experience. So I'll leave you with that for today.