Logic Seminar

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