The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics (Oxford Landmark Science)

by Roger Penrose

Turing showed that indeed there is not. His argument was essentially the following. We first suppose that, on the contrary, there is such an algorithm.* Then there must be some Turing machine H which ‘decides’ whether or not the nth Turing machine, when acting on the number m, eventually stops. Let us say that it outputs the tape numbered O if it does not stop and 1 if it does: Here, one might take the coding of the pair (n, m) to follow the same rule as we adopted for the universal machine U. However this could run into the technical problem that for some number n (e.g. n = 7), Tn is not correctly specified; and the marker 111101 would be inadequate to separate n from m on the tape. To obviate this problem, let us assume that n is coded using the expanded binary notation rather than just the binary notation, with m in ordinary binary, as before. Then the marker 110 will actually be sufficient to separate n from m. The use of the semicolon in H(n; m), as distinct from the comma in U(n, m) is to indicate this change. Now let us imagine an infinite array, which lists all the outputs of all possible Turing machines acting on all the possible different inputs. The nth row of the array displays the output of the nth Turing machine, as applied to the various inputs 0, 1, 2, 3, 4, . . . : In the above table I have cheated a little, and not listed the Turing machines as they are actually numbered. To have done so would have yielded a list that looks much too boring to begin with, ...