Halting Problem

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.