The Halting Problem

William J. Rapaport

Department of Computer Science and Engineering,
Department of Philosophy,
Department of Linguistics,
and Center for Cognitive Science
State University of New York at Buffalo,
Buffalo, NY 14260-2000

Last Update: 3 February 2007

Note: NEW or UPDATED material is highlighted

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

Question: Is there a computer program (e.g., a program for a Turing machine) that takes as input:

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

Call the program "H". Since H's input is C and i, we can refer to H and its input as:


  1. You can imagine that H(C,i) works as follows:

  2. However, we can't answer the question whether C halts on i by just running C on i:

Answer: No! There is no such program H(C,i).

Proof (sketch):

Assume by way of contradiction that there is such a program H.

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

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).

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

Now consider H*(C,C). (This step is called "diagonalization".) I.e., suppose you code up program C as a Gödel 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.

Now code H* as a number! And consider H*(H*,H*): In other words, code up H* as a Gödel 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!

So, If H* halts (outputting "no"), 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.

Copyright © 2001-2007 by William J. Rapaport (
file: halting-problem-20070203.html