1.Previous
3.Next

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. Now assume f was the halting function h. If g(e) is defined (g(e) = 0 in this case), then the program e halts on input e, thus f(e,e) = 1. But g(e) = 0 only when f(e,e) = 0, contradicting

1.Previous
3.Next