The Halting Problem

The Halting Problem provides an example of a non-computable problem.

Recall that a problem is computable if and only if there is an algorithm (i.e., a computer program) that computes its solution. See "What Is Computation?"

Question: Is there a non-computable problem? That is, is there a problem such that there's no algorithm that computes its solution?

Note that if everything is computable, then "computability" isn't a very interesting concept! It turns out that there is a non-computable problem; moreover, it's an interesting problem, namely, the problem of determining whether any given computer program halts.

Note that there's a potential ambiguity between:
1. Is there a computer program that takes as input any computer program C and any input i, and yields as output an answer to the question whether C halts on i.
2. Given a particular computer program C and input i, is there a computer program that tells you whether that particular C halts on that particular i.

The first is the Halting Problem, and is uncomputable. The second is not the Halting Problem, and is sometimes computable. (For instance, you know that this program loops: WHILE true DO anything.)

To prove that there is no computer program that can determine whether any arbitrary program halts, we need to prove that something does not exist. The best way to do this is to use a "proof by contradiction".

A "proof by contradiction" (also called a "proof by way of contradiction", a "proof for the sake of the argument, or a "reductio ad absurdum" (reduction to absurdity)), works as follows:
To prove P, assume not-P and derive a contradiction.
Since not-P implies a contradiction, P must have been true.
(For more info online, see Proof by Contradiction.)

The Halting Problem: Is there a computer program (e.g., a program for a Turing machine) that takes two things as input:

1. a computer program C, and
2. C's input (suppose C's input is an integer; call it "i")

• "yes", if C halts on i
• "no", otherwise (i.e., if C goes into an infinite loop on i)

Call the program (whose existence we're wondering about) "H". Since H's input is C and i, let's refer to H together with its two inputs as:

H(C,i)

Notes:

1. You can imagine that H(C,i) works as follows:
   1. H gives C its input, i,
   2. Then H simulates what C does with i.
   3. If C halts on i, then H outputs "yes" (i.e., "yes, C halts");
   4. Otherwise (if C loops on i), H outputs "no" (i.e., "no, C loops").

2. However, we can't answer the question whether C halts on i by just running C on i, because:
   • if it halts, we know it halts, but...
   • if it loops, how would we know it loops?
     (It might just be taking a very long time to halt.)

Solution to the Halting Problem:
No! There is no such program H(C,i) that tells us whether a program halts on its input.

Proof (sketch):

Assume, for the sake of the argument, that there is such a program H.

Now consider another program, H*, which works as follows:
H* is just like H, except that:

• H* loops if C halts on i (remember: H halts and outputs "yes" if C halts on i), and
• H* halts and outputs "no" if C loops on i (just like H does).

Note: If H exists, so does H*. I.e., we can turn H into H* as follows:

• if H were to output "yes", then let H* go into an infinite loop.
• More precisely, suppose that the last line of H is this:
  • IF C(i) halts THEN
         print("yes") & halt
    ELSE print("no") & halt

• Then let H* be just like H, except that its last line is this:
  • IF C(i) halts THEN
         WHILE true DO BEGIN END
    ELSE print("no") & halt

• Note that H*'s new last line involves an infinite loop "WHILE true DO BEGIN END". Since the Boolean test "true" will never be false, H* will always do nothing forever if it reaches this point. (If you are uncomfortable with the "no-op" or "do-nothing" command "BEGIN END", just replace it with something equally silly, like "BEGIN recite-the-alphabet END". The important point is that whatever you put between "BEGIN" and "END" will be done forever.)

Next, code C as a number, so that it can be treated as input to itself.

Digression: There are several ways to do this.
1. The easiest is to replace every symbol in C's program by its ASCII code, and then string all the codes together to form a HUGE binary numeral.

2. Turing proposed a similar method in his original paper on Turing machines.

3. And a third method is due to Kurt Gödel. To code any text, including a computer program, as a number in such a way that you could also decode it, begin by coding each symbol in the text as a unique number (e.g., using ASCII). Suppose that these numbers, in order, are L1, L2, L3, etc. (where L1 codes the first symbol in the text, L2 codes the second, etc.). Then compute the following number:
   2^L1 * 3^L2 * 5^L3 * 7^L4 * ...
   where each factor is the nth prime raised to the Ln power. By a theorem of number theory, this can be uniquely factored, the exponents can be recovered, and then they can be decoded to yield the original text. (Gödel numbering is actually a bit more complicated than this. For more info online, see Godel Numbering or What is Godel's Theorem?.)

I.e., suppose you code up program C as a number, use it as input to program C itself, and then let H* do its job on that pair of inputs. By the definition of H*, H*(C,C) loops if C halts on C, and it outputs "no" if C loops on C.

E.g., using our code above, the relevant line of H* will (replacing the infinite WHILE loop with the name "loop") become:

• IF C(C) halts THEN
       loop
  ELSE print("no") & halt

Now code H* as a number! And consider H*(H*,H*): In other words, code up H* as a number, use it as input to program H* itself, and then let H* do its job on that pair of inputs. Again, by the definition of H*, H*(H*,H*) loops if H* halts on H*, and it outputs "no" if H* loops on H*. But outputting "no" means that it halts!

E.g., using our code above, the relevant line of H* will (replacing the infinite WHILE loop with the name "loop") become:

• IF H*(H*) halts THEN loop
  ELSE print("no") & halt

So, If H* halts, then it loops, and if H* loops, then it halts. It loops if and only if it halts.

But that's a contradiction. So, there is no such H*. So, there is no such program as H. QED.

In other words, the Halting Problem is not computable.