The Halting Problem

Back when I was a PhD student, I needed a succinct way to summarize the Halting Problem, one of the core demonstrations of the limits of computation. There weren't a lot of online resources available at the time, so I wrote up this explanation. It appears that people continue to find it useful after all these years (the Internet Archive records a version from August 1999!), so I'm keeping it around.

Terminology

First of all, I'll be precise about some of the terms I'm going to use here.

A problem is a yes/no question that we ask of a particular input. Here are some sample problems:

An algorithm is a solution to a problem if it correctly provides the appropriate yes/no answer to the problem, and is guaranteed to always run in a finite amount of time.

A problem is decidable if it has a solution. If there is no algorithm that solves the problem in a finite amount of time, the problem is undecidable.

Turing's Argument

Are all problems decidable? Given enough thought, can we always come up with a well-defined procedure that takes some input and answers a given question about it? At the start of the 20th century, the belief was that this was true. Mathematicians (there were no computer scientists back then!) believed that we would eventually discover tools that we could use to answer any question we wanted (provided we could express it in the language of logic).

In 1931, Kurt Gödel shocked them all by proving that this was impossible. Using some very clever techniques, he showed that as soon as we devise a system that's sufficiently powerful and well-behaved to encompass mathematical reasoning, that system will necessarily contain a statement that we could never prove is true, even though it is true.

A few years later, Alan Turing proved an analogous theorem in Computer science. He showed that there must exist undecidable problems, questions for which there is no definable solution. His proof relied on some of the same clever techniques used by Gödel. Here, I present an adaptation of Turing's proof.

Here's a problem: given a computer program and some input to that program, will the program go into an infinite loop when fed that input? One could imagine this being a useful tool - you could detect infinite loops in your program before you ever ran it, saving yourself some debugging nightmares later. Note that the naive solution, running the program on the input and waiting to see if it stops, isn't valid because it could potentially run forever. You don't learn anything.

Assume that I was particularly inspired one day and I managed to write a solution to the halting problem. It might look something like this: 


  bool would_it_stop( char * program, char * input ) {
      if( something terribly clever ) {
          return true;
      } else {
          return false;
      }
  }

Don't worry about the specifics of the something terribly clever ; just assume I managed to write it somehow.

I could now use this program to check, without actually running a program, whether it will loop forever on a particular input. One input that might be of interest would be the program itself. Remember that the program is, at some level, just a bunch of data. In this case, the program is some characters that decribe instructions for doing something. There's nothing wrong with running a program and passing in the program itself as input. We could write a function to do that as follows: 


  bool stops_on_self( char * program ) {
      return would_it_stop( program, program );
  }

But now I've set myself up to do something very clever. This is where all the insight comes in. I'm going to cause everything to get all mixed up by deliberately including an infinite loop in a small program that detects infinite loops! Here it is: 


 bool bobs_yer_uncle( char * program ) {
     if( stops_on_self( program ) ) {
        while( 1 ) {}
        return false;
    } else {
        return true;
    }
 }

What's the meaning of this strange function? Well, let's think back for a second. I claimed that would_it_stop was a solution to the halting problem. That is, it's an algorithm that always terminates, and answers whether or not a program will loop forever on a given input. stops_on_self isn't much more complicated - it just passes the program twice to would_it_stop - once as instructions, and once as input. bobs_yer_uncle is just slightly more complicated. Given a program program, if stops_on_self( program ) is true, bobs_yer_uncle goes into an infinite loop (albeit a very simple one). Otherwise, it stops and returns true.

But here's the paradox. What happens when I try bobs_yer_uncle on itself? Well, clearly one of two things can happen: either it runs forever, or it stops and returns true, depending on whether the call to stops_on_self returns true or false.

We have therefore led ourselves to a contradiction. bobs_yer_uncle stops if and only if it runs forever. Since this is impossible, one of our assumptions must be invalid. By tracing our reasoning backwards, we find that it is therefore impossible to have written would_it_stop in the first place. In other words, the halting problem is undecidable.

In some sense, this problem (or some related formulation) is the canonical undecidable problem. There are countless other undecidable problems, which can often be expressed in terms of some simple question about a computer program. For example:

It turns out that these sorts of problems are all equivalent to the halting problem, in the sense that given a solution to one of them, you could write a solution to any of the other ones. The reasons why that is possible are interesting, but beyond the scope of the last sentence of this document.