Halting Problem
Take the coding Υ of the programs (for Turing Machine) , which enumerates all programs. Based on this coding (and the list of all programs), we can define the Halting Function h such that
(1) If P with Υ(P)=n stops with input m, then h(n, m) = 1, and
If P with Υ(P)=n does not stop with input m, then h(n, m) = 0.
Is this function h Turing-computable? Notice that this function h is defined over all programs and inputs.
Suppose there is a program H which computes h (in other words, h is Turing-computable); then
(2) If P with Υ(P)=n stops with input m, then @n,m ¨ 1 according to H, and
If P with Υ(P)=n does not stop with input m, then @n,m ¨ 0 according to H.
Next, (3) we can easily construct a program L which, with input 1, does not stop, and with input 0, stops.
With these preparations, we can construct the following program K:
(4) 1. right to 0, right, mark, left, left to 0
2. I(S), H, L
This program K, operates as follows, when an input n is given:
n ¨ n, 0 ¨ n, n @according to instruction 1 and I(S);
and then for the program P with Υ(P)=n (as in (2)) and input n,
(5) If P with Υ(P)=n stops with input n, then @n,n ¨ 1 according to H, and
If P with Υ(P)=n does not stop with input n, then @n,n ¨ 0 according to H.
Finally, applying the program L,
(6) If P with Υ(P)=n stops with input n, then since@n,n ¨ 1 according to H, K does not stop; and
If P with Υ(P)=n does not stop with input n, then since@n,n ¨ 0 according to H, K stops.
Now, notice that K has the code Υ(K)=k, since it is also a program. Now the crucial question: What is going to happen if K operates with input k (its own code)? According to (5),
(7) If K with Υ(K)=k stops with input k, then @k,k ¨ 1 according to H, and
If K with Υ(K)=k does not stop with input k, then @k,k ¨ 0 according to H.
Now applying the last part L of the instruction 2 of K (see (2)) , we have the following result:
(8) If K with Υ(K)=k stops with input k, then @k,k ¨ 1 according to H, and therefore K does not stop according to L; and If K with Υ(K)=k does not stop with input k, then @k,k ¨ 0 according to H, and therefore K stops.
But obviously this is a contradiction! This contradiction is derived from our initial assumption that h is Turing-computable; thus we have to conclude that this assumption was wrong, that is, h is not Turing -computable. The upshot is summarized in the following table.
If K stops with its own code k as input, then K does not stop; and if K does not stop with its own code k as input, then K stops. This contradiction shows that the halting function h is not Turing-computable. If you know Cantor's diagonal argument, compare the preceding construction of K with Cantor's original argument; where does the diagonalization appear in K?
Last modified May 27, 2008. (c) Soshichi Uchii