Halting Problem - Sketch of Proof

Sketch of Proof

The proof shows there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x; that is, the following function h is not computable (Penrose 1990, p. 57–63):

Here program i refers to the i th program in an enumeration of all the programs of a fixed Turing-complete model of computation.

f(i,j)		i	i	i	i	i	i
		1	2	3	4	5	6
j	1	1	0	0	1	0	1
j	2	0	0	0	1	0	0
j	3	0	1	0	1	0	1
j	4	1	0	0	1	0	0
j	5	0	0	0	1	1	1
j	6	1	1	0	0	1	0
	f(i,i)	1	0	0	1	1	0
	g(i)	U	0	0	U	U	0

The proof proceeds by directly establishing that every total computable function with two arguments differs from the required function h. To this end, given any total computable binary function f, the following partial function g is also computable by some program e:

The verification that g is computable relies on the following constructs (or their equivalents):

• computable subprograms (the program that computes f is a subprogram in program e),
• duplication of values (program e computes the inputs i,i for f from the input i for g),
• conditional branching (program e selects between two results depending on the value it computes for f(i,i)),
• not producing a defined result (for example, by looping forever),
• returning a value of 0.

The following pseudocode illustrates a straightforward way to compute g:

procedure compute_g(i): if f(i,i) == 0 then return 0 else loop forever

Because g is partial computable, there must be a program e that computes g, by the assumption that the model of computation is Turing-complete. This program is one of all the programs on which the halting function h is defined. The next step of the proof shows that h(e,e) will not have the same value as f(e,e).

It follows from the definition of g that exactly one of the following two cases must hold:

• g(e) = f(e,e) = 0. In this case h(e,e) = 1, because program e halts on input e.
• g(e) is undefined and f(e,e) ≠ 0. In this case h(e,e) = 0, because program e does not halt on input e.

In either case, f cannot be the same function as h. Because f was an arbitrary total computable function with two arguments, all such functions must differ from h.

This proof is analogous to Cantor's diagonal argument. One may visualize a two-dimensional array with one column and one row for each natural number, as indicated in the table above. The value of f(i,j) is placed at column i, row j. Because f is assumed to be a total computable function, any element of the array can be calculated using f. The construction of the function g can be visualized using the main diagonal of this array. If the array has a 0 at position (i,i), then g(i) is 0. Otherwise, g(i) is undefined. The contradiction comes from the fact that there is some column e of the array corresponding to g itself. If f were the halting function h, there would be a 1 at position (e,e) if and only if g(e) is defined. But g is constructed so that g(e) is defined if and only if there is a 0 in position (e,e).