The Halting Problem
Last Update: 3 February 2007
Note:
or
material is highlighted
|
|
The Halting Problem provides an example of a non-computable function.
Recall that a function is computable if and only if there is an
algorithm (i.e., a computer program) that computes it. See "What Is Computation?"
Question: Is there a computer program (e.g., a program for a
Turing machine) that takes as input:
- a computer program C, and
- C's input (suppose it's an integer; call it "i")
and that outputs:
- "yes", if C halts on i
- "no", otherwise (i.e., if C loops on i)
Call the program "H". Since H's input is C and i, we can refer to H and
its input as:
Notes:
- You can imagine that H(C,i) works as follows:
H gives C its input, i, and then runs C on i.
If C halts on i, then H outputs "yes";
otherwise, H outputs "no".
- However, we can't answer the question whether C halts on i by just running C
on i:
- 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.)
Answer: No! There is no such program H(C,i).
- I.e., H(C,i) is a non-computable function.
Proof (sketch):
Assume by way of contradiction that there is such a program H.
A proof by way of contradiction, or "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.
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 outputs "yes" if C halts on i), and
- H* 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).
Next, code C as a number, so that it can be treated as input to itself.
Digression: - This is an insight 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?.)
- Turing himself has an even simpler way to code symbols;
see Turing 1936, §5 ("Enumeration of Computable
Sequences").
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
(
rapaport@cse.buffalo.edu)
file: halting-problem-20070203.html