The Halting Problemmmmmm(HALT)

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 \psi. Given \psi‘s basic functionality, the ability to tell whether an input program will ever terminate, we can create a new program \Psi by extending \psi with the following criteria:

(1) \Psi halts if any inputted program \xi never halts.
(2) \Psi never halts if any inputted program \xi halts.

So if we write this out, it looks like this:

If \xi ( \ldots ) halts (i.e. if \Psi ( \xi ( \ldots )) is true), then \Psi doesn’t halt. If \xi ( \ldots ) doesn’t halt (i.e. if \Psi ( \xi ( \ldots )) is false), \Psi 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 \xi be \Psi, then we get the following:

If \Psi ( \Psi ( \ldots )) is true (i.e. if \Psi ( ... ) halts), then \Psi doesn’t halt. If \Psi (  \Psi ( \ldots )) is false (i.e. if \Psi ( ... ) doesn’t halt), then \Psi halts. This obviously makes no sense. Thus, \Psi and, by implication, \psi 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 \psi. 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

Advertisements

2 responses to this post.

  1. […] Incompl-ten-ss Th–rems Last time we talked about the Halting Problem, and we came away with the conclusion that it was […]

    Reply

  2. […] do computers require approximations? Well, let’s go back a few posts, when we discussed the Halting Problem. Remember that some programs run forever. We can construct such a program pretty […]

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: