Roger Penrose Quote

In order for A to apply to computations generally, we shall need a way of coding all the different computations C(n) so that A can use this coding for its action. All the possible different computations C can in fact be listed, say asC0, C1, C2, C3, C4, C5,...,and we can refer to Cq as the qth computation. When such a computation is applied to a particular number n, we shall writeC0(n), C1(n), C2(n), C3(n), C4(n), C5(n),....We can take this ordering as being given, say, as some kind of numerical ordering of computer programs. (To be explicit, we could, if desired, take this ordering as being provided by the Turing-machine numbering given in ENM, so that then the computation Cq(n) is the action of the qth Turing machine Tq acting on n.) One technical thing that is important here is that this listing is computable, i.e. there is a single computation Cx that gives us Cq when it is presented with q, or, more precisely, the computation Cx acts on the pair of numbers q, n (i.e. q followed by n) to give Cq(n).The procedure A can now be thought of as a particular computation that, when presented with the pair of numbers q,n, tries to ascertain that the computation Cq(n) will never ultimately halt. Thus, when the computation A terminates, we shall have a demonstration that Cq(n) does not halt. Although, as stated earlier, we are shortly going to try to imagine that A might be a formalization of all the procedures that are available to human mathematicians for validly deciding that computations never will halt, it is not at all necessary for us to think of A in this way just now. A is just any sound set of computational rules for ascertaining that some computations Cq(n) do not ever halt. Being dependent upon the two numbers q and n, the computation that A performs can be written A(q,n), and we have:(H) If A(q,n) stops, then Cq(n) does not stop.Now let us consider the particular statements (H) for which q is put equal to n. This may seem an odd thing to do, but it is perfectly legitimate. (This is the first step in the powerful 'diagonal slash', a procedure discovered by the highly original and influential nineteenth-century Danish/Russian/German mathematician Georg Cantor, central to the arguments of both Godel and Turing.)With q equal to n, we now have:(I) If A(n,n) stops, then Cn(n) does not stop.We now notice that A(n,n) depends upon just one number n, not two, so it must be one of the computations C0,C1,C2,C3,...(as applied to n), since this was supposed to be a listing of all the computations that can be performed on a single natural number n. Let us suppose that it is in fact Ck, so we have:(J) A(n,n) = Ck(n)Now examine the particular value n=k. (This is the second part of Cantor's diagonal slash!) We have, from (J),(K) A(k,k) = Ck(k)and, from (I), with n=k:(L) If A(k,k) stops, then Ck(k) does not stop.Substituting (K) in (L), we find:(M) If Ck(k) stops, then Ck(k) does not stop.From this, we must deduce that the computation Ck(k) does not in fact stop. (For if it did then it does not, according to (M)! But A(k,k) cannot stop either, since by (K), it is the same as Ck(k). Thus, our procedure A is incapable of ascertaining that this particular computation Ck(k) does not stop even though it does not.Moreover, if we know that A is sound, then we know that Ck(k) does not stop. Thus, we know something that A is unable to ascertain. It follows that A cannot encapsulate our understanding.