Turing's paper actually proves something much more interesting than just the existence of unsolvable problems, what he calls undecidable problems. But again, even like 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 know, you can imagine you might, uh, think about the problem of finding bugs in programs. Uh, bugs mean errors in programs. You probably knew that.
If, if you don't know why they're called that, it's because those same computer systems in the late nineteen-forties 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 sort of resurrect the computer because literally a bug got in the vacuum tubes. So that's why we still call error, errors in programs bugs to this day. Anyways, you want computer code to be correct, right? You don't want someone to hack into your, uh, 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, you know, speaking now, speaking in twenty twenty-six, 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. Now, here's a very, very special case of trying to find a bug in a program, something called the halting problem, okay? So I give you a computer program.
I give you some code. Think of it as like, I don't know, two hundred lines of Python or any other programming language you might be familiar with. So I give you this, you know, really short, just like a few pages, few pages of code, and I ask you, it's like, "If you ran this program, would it complete? Would it halt? Would it stop?
Or would it run forever?" Okay? For example, because it gets caught in an infinite loop. Okay, I just wanna know which of those two things is the case. And, um, 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? And, um, your first thought might be like, "Easy, give me the program. I'll run it. I'll see what happens." Okay? And if it halts, great.
You say like, "Yeah, the program halts. I ran it. I saw it from my own-- with my own two eyes." Okay, fine. But what if you run the program, and it's like ten minutes later, and it hasn't halted. It's still running.
You're like, "Okay, uh, let's give it a little more time." Okay? Maybe you run it overnight. You wake up the next morning, and it's still running. You're like, "All right, um, maybe it's in an infinite loop, but, you know, maybe it's actually doing like 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. Like, what else could possibly be going on?" But remember, what did we say?
We said even very short programs can exhibit tremendously complex behavior. And again, these sort of, you know, the computation of these busy beeber-- busy beaver functions that I mentioned earlier are the classic compu-- classic example of very short computations running for a, a obscene number of steps. So the bottom line is, is that even if you've run it for a year and it hasn't halted, you have no idea whether it's gonna halt tomorrow or not, okay? 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, okay? 'Cause you are never sure that it's in an infinite loop. You're never sure that it's not going to halt tomorrow.
But the question is like, okay, but that's like 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 the halting problem. "Look, it's two hundred lines of code.
Stare at it, think about it, analyze it. Just tell me the answer." Right? That's the halting problem. The halting problem, Turing showed undecidable, okay? There's literally no automated procedure that will take your two hundred 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 twenty twenty-six technology, okay? 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.
And to s- to see the connection between this undecidability of the halting problem and the decision problem that Hilbert asked about, right? So 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, you know, once-- if, if, for example, you successfully figured out no proof with at most ten thousand lines is a proof of this statement, you cannot directly conclude that this statement is unprovable, right?
Because there might be a proof with just one more line, ten thousand and one lines, that establishes that statement. 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, uh, via any other method. Now mind you, there will be mathematical statements where we'll be able to find the proof for it, right? 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 pr- 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, you know, some mathematical statement and tells you whether it's provable or not.