Diagonal arguments

Similar arguments were used by Georg Cantor in 1891 to show that there must be more real numbers than integers and by Alan Turing in 1936 to show that the problem of enumerating computable real numbers is unsolvable. One might imagine that it should be possible to set up a function f[i, n] which if given successive integers i would give the n^th base 2 digit in every possible real number. But what about the number whose n^th digit is 1 - f[n, n]? This is still a real number, yet it cannot be generated by f[i, n] for any i—thus showing that there are more real numbers than integers. Analogously, one might imagine that it should be possible to have a function f[i, n] which enumerates all possible programs that always halt, and specifies a digit in their output when given input n. But what about the program with output 1 - f[n, n]? This program always halts, yet it does not correspond to any possible value of i—even though universality implies that any program should be encodable by a single integer i. And the only possible conclusion from this is that f[i, n] cannot in fact be implemented as a program that always halts—thus demonstrating that the computable real numbers cannot explicitly be enumerated. (Closely related is the undecidability of the problem discussed on page 1137 of whether a system halts given any particular input.) (See also pages 907 and 1162.)