Last time we talked about Turing machines (and the madman who dreamt of them). This time we’re going to discuss one seemingly trivial thought experiment about Turing machines that turns out to have tremendous significance for both computing and for mathematics. It is called “the Halting Problem”.
The Halting Problem asks one rather simple question: Does there exist a program which can, when given any program as input, determine whether that input terminates or not?
Let’s assume for a moment that such a program does exist, and call that program . Given ‘s basic functionality, the ability to tell whether an input program will ever terminate, we can create a new program by extending with the following criteria:
(1) halts if any inputted program never halts.
(2) never halts if any inputted program halts.
So if we write this out, it looks like this:
If halts (i.e. if is true), then doesn’t halt. If doesn’t halt (i.e. if is false), does. This condition is imposed upon the program because as you’ll quickly see, it provides a contradiction. If such a program actually existed, such a contradiction would not occur.
So where’s the contradiction? Well if we let be , then we get the following:
If is true (i.e. if halts), then doesn’t halt. If is false (i.e. if doesn’t halt), then halts. This obviously makes no sense. Thus, and, by implication, cannot have existed.
Are you convinced? In some way, the halting problem asks, “Does the liar’s paradox have a resolution?”. The liar’s paradox comes in all sorts of forms. One you might recognize is the “Opposite Day” game kids play. Consider the following declaration: “Today is Opposite Day; everything you say means the opposite”. Well if you claim on Opposite Day that it’s Opposite Day, then you’re actually claiming it isn’t Opposite Day. But if it isn’t Opposite Day, then your original claim was actually true, in which case it was false, in which case it was true, and so on. The problem recycles back and forth between true and false. It would appear that this scenario does not halt. But what if the original claim was just false. That is, what if whomever said it was Opposite Day was just lying. Then there’s no paradox, and the problem is resolved.
This brings up the real reason why the Halting Problem has no solution (or in computing terminology, is “undecidable”). Our original question was, “Does there exist a program which can, when given any program as input, determine whether that input terminates or not?” The problem, given the previous scenario, seems obvious. We’re asking if there’s an absolute answer to a question that may have extenuating circumstances. Obviously, no, such a thing doesn’t exist. If I’m simply lying when I say “It’s Opposite Day”, then the liar’s paradox halts. But if I’m not, then it doesn’t halt. In other words, the problem depends on whether or not I’m lying. More generally, any problem depends on certain conditions, and those conditions can vary. Therefore there’s no possible way to code a program such as . We’re just lacking too much information about each individual program and each of their possibly different conditions and inputs.
Next time . . . : Godel’s Two Incompleteness Theorems