Author: Roger Penrose
Quotes of Author: Roger Penrose
The thrust of Godel's argument for our purposes is that it shows us how to go beyond any given set of computational rules that we believe to be sound, and obtain a further rule, not contained in those rules, that we must believe to be sound also, namely the rule asserting the consistency of the original rules. The essential point, for our purposes, is:belief in soundness implies belief in consistency.We have no right to use the rules of a formal system F, and to believe that the results that we derive from it are actually true, unless we also believe in the consistency of that formal system. {For example, if F were inconsistent, then we could deduce, as TRUE, the statement '1=2', which is certainly not true!} Thus, if we believe that we are actually doing mathematics when we use some formal system F, then we must also be prepared to accept reasoning that goes beyond the limitations of the system F, whatever that system F may be. book-quoteIn 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. book-quoteQ5. Have not I merely shown that it is possible to outdo just a particular algorithmic procedure, A, by defeating it with the computation Cq{n}? Why does this show that I can do better than any A whatsoever?The argument certainly does show that we can do better than any algorithm. This is the whole point of a reductio ad absurdum argument of this kind that I have used here. I think that an analogy might be helpful here. Some readers will know of Euclid's argument that there is no largest prime number. This, also, is a reductio ad absurdum. Euclid's argument is as follows. Suppose, on the contrary, that there is a largest prime; call it p. Now consider the product N of all the primes up to p and add 1:N=2*3*5*...*p+1.N is certainly larger than p, but it cannot be divisible by any of the prime numbers 2,3,5...,p {since it leaves the remainder 1 on division}; so either N is the required prime itself or it is composite-in which case it is divisible by a prime larger than p. Either way, there would have to be a prime larger than p, which contradicts the initial assumption that p is the largest prime. Hence there is no largest prime. The argument, being a reductio ad absurdum, does not merely show that a particular prime p can be defeated by finding a larger one; it shows that there cannot be any largest prime at all. Likewise, the Godel-Turing argument above does not merely show that a particular algorithm A can be defeated, it shows that there cannot be any {knowably sound} algorithm at all that is equivalent to the insights that we use to ascertain that certain computations do not stop. book-quoteIt is a common misconception, in the spirit of the sentiments expressed in Q16, that Godel's theorem shows that there are many different kinds of arithmetic, each of which is equally valid. The particular arithmetic that we may happen to choose to work with would, accordingly, be defined merely by some arbitrarily chosen formal system. Godel's theorem shows that none of these formal systems, if consistent, can be complete; so-it is argued-we can keep adjoining new axioms, according to our whim, and obtain all kinds of alternative consistent systems within which we may choose to work. The comparison is sometimes made with the situation that occurred with Euclidean geometry. For some 21 centuries it was believed that Euclidean geometry was the only geometry possible. But when, in the eighteenth century, mathematicians such as Gauss, Lobachevsky, and Bolyai showed that indeed there are alternatives that are equally possible, the matter of geometry was seemingly removed from the absolute to the arbitrary. Likewise, it is often argued, Godel showed that arithmetic, also, is a matter of arbitrary choice, any one set of consistent axioms being as good as any other. book-quoteSpecifically, the awareness that I claim is demonstrably non-computational is our understanding of the properties of natural numbers 0,1,2,3,4,....{One might even say that our concept of a natural number is, in a sense, a form of non-geometric 'visualization'.} We shall see in 2.5, by a readily accessible form of Godel's theorem {cf. response to query Q16}, that this understanding is something that cannot be simulated computationally. From time to time one hears that some computer system has been 'trained' so as to 'understand' the concept of natural numbers. However, this cannot be true, as we shall see. It is our awareness of what a 'number' can actually mean that enables us to latch on to the correct concept. When we have this correct concept, we can-at least in principle-provide the correct answers to families of questions about numbers that are put to us, when no finite set of rules can do this. With only rules and no direct awareness, a computer-controlled robot {like Deep Thought} would be necessarily limited in ways in which we are not limited ourselves-although if we give the robot clever enough rules for its behaviour it may perform prodigious feats, some of which lie far beyond unaided human capabilities in specific narrowly enough defined areas, and it might be able to fool us, for some while, into thinking that it also possesses awareness. book-quote
