Joel David Hamkins: prediction

Transcript context

……to be able to make a prediction? The main lesson of computability theory, in my view, is that it’s never the case that you can have a thorough understanding of the behavior of a program by looking at the program, and that the content of what you learn from a program, I mean, in the most general case, is always obtained just by running it and looking at the behavior. And the proof of that is there’s a theorem called Rice’s Theorem, which makes that idea completely robust. But I want to just take a little detour towards another question riffing on something that you just said. Namely, one can ask the question, what is the behavior of a random program? So you have some formal computing language, you know, and you want to look at the collection of all programs of a certain size. Maybe there are only finitely many. And can you say something about the behavior of a randomly chosen one, like with a certain likelihood it will have a certain behavior? And the answer turns out to be extremely interesting. Once, years ago, Alexey Myasnikov asked me a question. He had this concept of a decision problem with a black hole, and what that means is it’s a decision problem which is possibly difficult in the worst case, but the difficulty was concentrated in a very tiny region called the black hole. And outside of that black hole, it was very easy. And so, for example, this kind of problem is a terrible problem to use if you’re basing your encryption scheme. You don’t want to use a black hole problem because if someone can rob the bank 95% of the time, then that’s not what you want, or even any nontrivial percent of the time is too dangerous. So you don’t want to use problems that are almost every case is easily solved as the basis of your encryption. And the question Alexey asked me was, “Does the halting problem have a black hole?” And so if we take, say, the standard model of Turing machines—it’s one-way infinite tape with zeros and ones on the tape and so on, the head moving back and forth, and it stops when it gets into the halt state—then it turns out we proved that there is a black hole. And what that means is there’s a computer procedure that decides correctly almost every instance of the halting problem. Even though the halting problem is not decidable, we can decide almost every instance. So more precisely, there’s a collection of Turing machine programs such that we can easily decide whether a program’s in that collection or not. And for the programs in the collection, we can decide the halting problem for those programs easily. ring machine programs such that we can easily decide whether a program’s in that collection or not. And for the programs in the collection, we can decide the halting problem for those programs easily. And furthermore, almost every program is in the collection in the sense that as the number of states becomes large, the proportion of programs in the collection goes to 100%. So the asymptotic density of the programs is one. And the proof was quite fascinating because it’s one of these situations where the theorem sounds really surprising, I think, to many people when I first tell it, I mean, to computability experts. Then it’s sort of intriguing to think that you can solve almost every instance of a halting problem. But then when they hear the proof, it’s completely a letdown. Unfortunately, nobody likes the theorem after the proof. And so the proof is so simple, though. If you know how a Turing machine operates, there’s this infinite paper tape on which the machine writes zeros and ones, and the head moves back and forth according to rigid instructions. And the instructions are all of the form: if the machine is in such and such a state and it’s reading such and such a symbol on the tape, then it should write this symbol on the tape, it should change to this new state specified, and it should either move left or right as specified. So a program consists of instructions like that. If you look at a program, one of the states is the halt state, and that’s when the program halts. But you can calculate how many programs don’t have any instruction that transitions to the halt state. You can easily calculate the proportion. And in the limit, it goes to 1 over E squared, 13 and a half percent. If you calculate the limit, the proportion of programs with end states that don’t ever halt because they don’t have any instruction saying halt— —those programs obviously never halt because they can’t halt. They don’t have any instruction that says halt.…

Stored transcript either side of the excerpt. The highlighted words are the published quote; the surrounding text is unedited source, never generated.