Book: Shadows of the Mind: A Search for the Missing Science of Consciousness
Quotes of Book: Shadows of the Mind: A Search
  1. Roger Penrose _ Shadows of the Mind: A Search

    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.
    book-quote
  2. Roger Penrose _ Shadows of the Mind: A Search

    Q5. 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-quote