Roger Penrose's book Shadows of the Mind may be purchasedfrom Amazon.Com |
---|

A Review of Shadows of the Mind by Roger Penrose

Department of Mathematics

Stanford University

Stanford, CA 94305-2125

U.S.A.

sf@csli.stanford.edu

Copyright (c) Solomon Feferman 1995

PSYCHE, 2(7), May 1995

http://psyche.cs.monash.edu.au/v2/psyche-2-07-feferman.html

REVIEW OF: Roger Penrose (1994)

1.2 I am only competent to say something substantive about the first part of the new effort, resting as it does to a considerable extent on a version of Gödel's (first) incompleteness theorem. Penrose had advanced that previously in ENM, but the line of argument was much criticized, as it had been in the past when advanced by others (e.g. J.R. Newman and E. Nagel, and J.R. Lucas) <2>. So now Penrose has gone to great lengths in SOTM to lay out his Gödelian argument and to try to defend it against all possible objections. I must say that even though I think Gödel's incompleteness theorems are among the most important of modern mathematical logic and raise fundamental questions about the nature of mathematical thought, and even though I am convinced of the extreme implausibility of a computational model of the mind, Penrose's Gödelian argument does nothing for me personally to bolster that point of view, and I suspect the same will be true in general of readers with similar convictions. On the other hand, I'm sure that those whose sympathies lie in the direction of a computational model of mind will find reasons to dismiss the Gödelian argument quickly on one ground or another without wading through its painful elaboration. If I'm right, this effort -- diligent as it is -- is largely wasted. Nevertheless, since Penrose has done it, I feel obliged to address at least the more technical aspects of his argument.

1.3 While I have disavowed competence concerning Part II of SOTM, I can't help registering my impression that the effort there is entirely quixotic. What Penrose aims to do is substitute one "nothing but" theory for another: in place of "the conscious mind is nothing but the action of a computer" he wishes to have "the conscious mind is nothing but the manifestation of sub-atomic physics". Can we really ever expect a completely reductive theory of one sort or another of human cognition? Surely, no one theory will serve to "explain" the myriad aspects of this phenomenon. As with any other scientific study of human beings -- inside and out -- such an enterprise will need to continue to make use of psychology, psycho-physics, physiology (neuro- and otherwise), biochemistry, molecular biology, physics (macro- and micro-) and who knows what all else (including computational models of all kinds). In my opinion Penrose's "missing science of consciousness" is a mirage.

2.2 Penrose's form of Gödel's incompleteness theorem is stated in terms of Turing machine computations as follows (pp. 74-75):

Theorem 1: Suppose A is a Turing machine which is such that whenever A halts on an input (q,n) then C_q(n) does not halt. Then for some k, C_k(k) does not halt, yet A does not halt on (k,k). In other words, if the halting of A is a sufficient condition for the non-halting of Turing machines then it is not a necessary condition for that; still more briefly: soundness of A implies incompleteness of A.2.3 The proof of Theorem 1 is just a variant of the standard diagonal argument, originating with Turing in 1937, that the halting problem for Turing machines is not effectively decidable. As a form, though, of Gödel's incompleteness theorem, it is very close to Kleene's generalized form of that result, established in 1943 and exposited in Kleene (1952) p. 302 as Theorem XIII. That makes use of a very general notion of formal system F, the main condition for which is that the set of "provable formulas" is effectively enumerable. Suppose in particular that F contains effectively given "formulas" phi(q,n) which are supposed to "express" the predicate P(q,n) which holds just in case C_q(n) does not halt. F is said to be

Theorem 2: If F is a formal system (in the general sense) which is sound for the predicate P then it is not complete for it. In particular, there is a k such that C_k(k) does not halt though F does not prove phi(k,k).2.4 Assuming Church's Thesis, Theorem 2 follows Theorem 1, since every recursively enumerable set of pairs (q,n) is the same as the set of inputs on which a Turing machine halts. Conversely, to obtain Theorem 1 from Theorem 2, simply take the "formula" phi(q,n) to be the pair (q,n) and the set of "provable formulas" of F to be the set of pairs on which A halts.

2.5 We must now examine the relationship of these results with the usual formulation of Gödel's incompleteness theorems. Here we deal with formal systems in the logical sense, i.e. systems F whose formulas are built up from basic arithmetical (and possibly other) relations by means of the propositional connectives and quantifiers and whose provable formulas are obtained from a given set of axioms (both logical and non-logical) by closing under certain rules of inference. Moreover, F is assumed to be effectively given, i.e. the set of axioms of F and its rules of inference are supposed to be effectively decidable, so that its set of provable formulas is effectively enumerable. Finally, F is supposed to be "sufficiently strong", i.e. contain a modicum F_0 of elementary number theory (or arithmetic). Over the years, the statement of Gödel's incompleteness theorems has been steadily strengthened by a steady weakening of what is assumed for F_0. In 1931, Gödel had taken it to be a version of simple type theory over a number-theoretical base, but he soon weakened that to a form of the first-order system of Peano Arithmetic PA. Subsequently, for Gödel's first incompleteness theorem, this was further weakened considerably to R.M. Robinson's fragment Q of arithmetic, and for the second incompleteness theorem to the subsystem Sigma_1-IA of PA based on induction applied only to Sigma_1 formulas. For details, see Gödel's 1931 and related papers in the original and in translation, with an introductory note by Kleene, in Gödel (1986), pp. 126ff, and the expositions in Kleene (1952), pp. 204-213 and Smorynski (1977). For simplicity, we assume throughout the following that F_0 is PA, and that F is an (effectively given) formal system in the logical sense which contains PA.

2.6 As Penrose notes, the class of PI_1 formulas is of special significance in connection with the Gödel theorems. These are ones of the form $forall(x) R(x)$, where R expresses an effectively decidable (recursive) property of the natural numbers and the intended range of 'x' is the set of natural numbers. Dual to this class is the class SIGMA_1 of formulas of the form $exists(x) S(x)$ where S is effectively decidable; in classical logic, these are equivalent to negations $not forall(x) not S(x)$ of PI_1 formulas. We may consider similarly PI_1 and SIGMA_1 formulas with free variables such as $forall(y) R(x,y)$ and $exists(y) S(x,y)$ with decidable R, S, resp.

2.7 The following examples are particularly relevant to the Gödel theorems:

(i) We have a decidable relation Proof_F(x,y) which expresses that y is (the Gödel number of) a proof in F of the formula (with number) x; then

(ii) the SIGMA_1 formula Prov_F(x):=$exists(y) Proof_F(x,y)$ expresses that the formula (with number) x is provable in F, while the PI_1 formula $forall(y) not Proof_F(x,y)$ expresses that x is not provable in F; in particular,

(iii) if c is the number of the formula $0=1$, the PI_1 formula Con(F) := $forall(y) not Proof_F(c,y)$ expresses that F is consistent. Next, (following Kleene), we have

(iv) a decidable relation T(z,x,y) which expresses that y is (the number of) a terminating computation at input x on the Turing machine C_z; so

(v) the SIGMA_1 formula $exists(y) T(z,x,y)$ expresses that C_z(x) halts, and

(vi) the PI_1 formula $forall(y) not T(z,x,y)$ expresses that C_z(x) does not halt; in particular,

(viii) for each k, the PI_1 sentence $forall(y) not T(k,k,y)$ expresses that C_k(k) does not halt.

2.8 The system F is said to be

Lemma 3: (i) F is complete for SIGMA_1 sentences. (ii) F is 1-consistent if and only if F is sound for SIGMA_1 sentences. (iii) F is consistent if and only if F is sound for PI_1 sentences.2.9 The idea for the proof of (ii) is that if F is 1-consistent and proves $exists(x) S(x)$ where S is decidable then there must exist an n such that S(n) holds, since otherwise we could prove $not S(n)$ for each n. The converse is immediate by definition. The idea for the proof of (iii) is that if F is consistent and proves $forall(x) R(x)$ with R decidable, then for each n, F proves R(n), hence R(n) must be true, for otherwise $not R(n)$ would be provable in F as a special case of (i).

2.10 The result (iii) of Lemma 3 is a fundamental observation due to Hilbert, since it shows that any success of his consistency program for a system F would establish the correctness of F for the "real" (i.e. PI_1) sentences.

2.11 For his completeness results, Gödel constructed a PI_1 sentence G(F) equivalent (in PA) to $forall(y) not Proof_F(g,y)$, where g is the Gödel number of G(F). Thus G(F) provably expresses of itself (via its Gödel number) that it is not provable in F.

Theorem 4. (Gödel's 1st incompleteness theorem).2.12 Now the hypothesis in (i) is equivalent by Lemma 3 to the soundness of F for PI_1 sentences, and since under this hypothesis the sentence $forall(y) not Proof_F(g,y)$ is true and hence G(F) is true, we conclude from the

(i) If F is consistent then G(F) is not provable in F.

(ii) If F is omega-consistent then $not G(F)$ is not provable in F.

Corollary 5. If F is sound for PI_1 sentences then F is not complete for them.2.13 In this form, the first part of Gödel's 1st incompleteness theorem is of the same character as Theorem 1 (Turing-Penrose) as well as Theorem 2 (Kleene). Note that the hypothesis of the second part of Theorem 4 can be replaced immediately by the assumption that F is 1-consistent. For if $not G(F)$ is provable in F then so also is $exists(y) Proof_F(g,y)$. But that sentence is false by the first part of the theorem. Note also that if $not G(F)$ is added to F as an axiom, and F is consistent, the resulting system is still consistent (by the first part of Theorem 4) but not 1-consistent, hence not omega-consistent.

2.14 In 1937, Rosser constructed a PI_1 sentence R(F) which is such that if F is consistent neither R(F) nor $not R(F)$ is provable in F. However, R(F) is less useful than G(F), as the following shows:

Theorem 6. (Gödel's 2nd incompleteness theorem).2.15 The idea of a proof of $Con(F) -> G(F)$ in (i) is to formalize in PA the proof of the first part of the 1st incompleteness theorem. The converse, that $G(F) -> Con(F)$, is trivial, since if any sentence is not provable in F then 0=1 is not provable in F.

(i) PA proves $Con(F) -> G(F)$.

(ii) Hence, if F is consistent then F does not prove Con(F), i.e. F does not prove its own consistency.

3.2 pp. 74-75 (sec. 2.5). The idea of a computational procedure A being

3.3 pp. 90-92 (sec. 2.8). In Penrose's account of Gödel's incompleteness theorem, he says (p. 91) that if a formal system is

3.4 Next on p. 91, Penrose introduces the notation 'Omega(F)' for the [formal] assertion that the system F is omega-consistent. He says that "Gödel's famous incompleteness theorem tells us that Omega(F) is

3.5 Penrose further says here that he will use the notation 'G(F)' for the [formal] assertion that F is consistent. He then says that Rosser's theorem tells us that if F is consistent then G(F) is not a theorem of F; but that is what Gödel's 2nd incompleteness theorem tells us, not Rosser's. Penrose further muddies the picture by saying that he will "not bother to draw a clear line between consistency and omega-consistency" in most of his discussions, but that "the version of the Gödel theorem that I [Penrose] have actually presented in section 2.5 is essentially the one that asserts that if F is omega-consistent, then it cannot be complete, being unable to assert Omega(F) as a theorem." Instead, as we have seen, what he showed in section 2.5 is a version of the first part of Gödel's incompleteness theorem, that if F is sound for PI_1 sentences [-> consistent] then G(F) is not a theorem of F.

3.6 On p. 92, Penrose says that in order to discuss the actions of Turing machines, F must contain the minimum operator (mu) symbol. It is true that, in Kleene's normal form theorem, the value of C_q(n) is of the form U(mu y.T(q,n,y)) when $exists(y) T(q,n,y)$ holds; but the statement of halting or non-halting of C_q(n) does not require the explicit presence of mu among the symbols of F.

3.7 p. 96. It is stated here that "...both Omega(F) and G(F) are PI_1 sentences." This is correct for G(F) but not for Omega(F) which is, instead, a sentence in PI_3 form, i.e. of the form $forall(x) exists(y) forall(z) R(x,y,z)$ with R decidable [work it out]. Even 1-consistency is a PI_2 sentence, which is not equivalent to a PI_1 sentence.

3.8 p. 108. Penrose says here that if F* and F** are obtained from F by adjoining G(F) and $not G(F)$ resp. as axioms, and if F is consistent then F* and F** are both consistent. This is correct for F** by ordinary logic, but not for F*. The following is a counter-example: let F be obtained from PA by adjoining $not G(PA)$ or, equivalently, $not Con(PA)$ as an axiom. Thus F is PA** in Penrose's notation, and so F is consistent. But in this case, since F* includes $Con(F)$ and PA is contained in F, we have that F* proves $Con(PA)$, so F* is inconsistent. What is needed to insure that F* is consistent is the assumption that F is 1-consistent (which is

3.9 pp. 109-110. The discussion of the non-categoricity of the first-order version of PA of Peano's axioms vs. the categoricity of the second-order version of those axioms is misleading since it lumps together first-order quantification with second-order quantification. What the latter does is allow one to quantify over properties P in the induction axiom, namely as $forall(P) [P(0) and forall(x) (P(x) -> P(Sx)) -> forall(x) P(x)]$. However, Penrose is right in saying that for this second-order axiom to guarantee categoricity we need to regard it semantically, i.e. to interpret the variable 'P' in 'forall(P)' as ranging over arbitrary subsets of the first-order domain of interpretation, and there is no effective formal system complete for this semantics (by Gödel's incompleteness theorem).

3.10 p. 112. In the discussion of Q18 it is asserted that we cannot "properly encapsulate 'soundness' or 'truth' within any formal system -- as follows by a famous theorem of Tarski". This settles definitely the earlier ambiguity between the notions of soundness used on pp. 74-75 and that of p. 91, i.e. here soundness is taken as truth of all sentences (at least all arithmetical ones); then Tarski's theorem on the non-definability of truth certainly applies provided the system F under consideration is consistent. Penrose goes on to say that for restricted notions of soundness we can prove in F, or even PA, that if F is sound then G(F) holds. In particular, he says that PA proves $Con(F) -> G(F)$. This is strange, because on p. 91 he said that he will use 'G(F)' for the formal statement that F is consistent, i.e. for 'Con(F)': but for that identification the implication is trivial. The implication $Con(F) -> G(F)$ is only of interest if one takes G(F) to be Gödel's sentence that expresses of itself that it is not provable in F (cf. Theorem 6(i) above). The next strange statement on p. 112 is that one can prove that 'F omega-consistent' implies 'Omega(F)', since on p. 91 Penrose defined Omega(F) to be the formal statement of the omega-consistency of F; on that identification the implication is once more trivial.

3.11 p. 114: The description of my results on Turing's ordinal logics is incorrect. First of all, the reference given is to Feferman (1988), which contains a historical exposition of Turing's seminal work (1939) and subsequent work on this subject (under the new name, transfinite recursive progressions of formal systems). The appropriate reference for my own original work there should have been Feferman (1962). It was Turing (not me) who showed in his 1939 paper that the ordinal logic obtained by iteration of adjunction of consistency statements starting with PA and proceeding through the recursive ordinals is complete for PI_1 statements (in fact at a surprisingly low level); Turing had hoped to improve this to completeness for PI_2 sentences. In my 1962 paper I proved that: (i) Turing's ordinal logic is incomplete for PI_2 sentences; (ii) the same holds for progressions based on transfinite iteration of the so-called local reflection principle; but (iii) one obtains completeness for

3.12 I have not detailed all the occurrences of technical errors that Penrose makes in connection with Gödel's incompleteness theorems in Ch. 2, many of which also propagate through Ch. 3. Given the weight that Penrose attaches to his Gödelian argument, all these errors should give one pause. One has here lots more of the "slapdash scholarship" that Martin Davis complained about in his commentary on ENM (1993, p.116), and they suggest that Penrose may stretch that scholarship perilously thin in areas distant from his own expertise. The main question, though, is whether these errors undermine the conclusions that he wishes to draw from the Gödelian argument. I don't think that they do, at least

4.2 The reformulation of incompleteness in terms of Turing machines in section 2.5 is of course important if one is to argue that mathematical thought is not mechanical, but it is

4.3 So on the face of it, mathematical thought as it is actually produced is not mechanical; I agree with Penrose that in this respect,

4.4 Penrose begins by stating as the main conclusion G from the Gödel-Turing incompleteness theorem: "Human mathematicians are not using a knowably sound algorithm in order to ascertain mathematical truth" (p. 76). More specifically, in terms of formal systems: if mathematicians can come to know that a system F is sound, then F cannot be used to ascertain the truth of the true PI_1 statement G(F). Now, as I have noted, there is an ambiguity in Penrose's use of the notion of soundness between that for PI_1 sentences and that for all sentences. All that the Gödel incompleteness theorem requires of F is the former, since that is equivalent to the consistency of F. But Penrose tends to emphasize the global notion of soundness and to tie it to his Platonistic philosophy of mathematics. The argument goes something as follows: how could we know that F is sound if we did not understand what F is about -- its intended interpretation -- and see that the axioms of F are all

4.5 Two problems with this argument are that (i) there may be other ways of recognizing the truth of G(F) than through a global notion of truth for F, and (ii) the assumption of an intended interpretation for set-theoretical formalisms is highly problematic. The first is what is achieved by proof theory. While it is generally agreed that Hilbert's program to establish the consistency of stronger and stronger formal systems by purely finitary proof-theoretical methods cannot be carried through as a result of Gödel's 2nd incompleteness theorem, a

4.6 Moving on to the philosophical issues raised by Platonism in set theory, Penrose is right in identifying Gödel as one of the foremost proponents of this position. However, I think it is fair to say that he has few adherents among philosophers of mathematics. Admittedly, every overall philosophy of mathematics has its difficulties, but Penrose make it seem that the Platonistic position is a matter of common consensus. This is not the case for those who have given these questions more than token attention. While one may well agree that questions of truth in the natural numbers are of a determinate character, already the assumption of a supposed definite totality of arbitrary sets of natural numbers is highly problematic. Indeed, Gödel himself, at least for a period in the 1930s, found this deeply troubling. In a previously unpublished lecture (*1933o in Gödel (1995)), he said that: "The result of the preceding discussion is that our axioms [for set theory], if interpreted as meaningful statements, necessarily presuppose a kind of Platonism, which cannot satisfy any critical mind and which does not even produce the conviction that they are consistent." (op.cit. p. 50). And Gödel continued to take proof-theoretical approaches to consistency seriously throughout his life (see also *1938a in Gödel (1995) and the introductory notes to that and *1933o). Incidentally, on p. 116 of SOTM, Penrose says that Paul Cohen, in the last section of his 1966 book on the independence of AC and CH from ZF set theory "reveals himself to be, like Gödel [and Penrose] a true Platonist for whom matters of mathematical truth are

4.7 Penrose reports in section 3.1 on what Gödel took the significance of his incompleteness theorems to be, via a quotation which had circulated some time back from Gödel's unpublished Gibbs lecture of 1951. That piece is now available in full as *1951 in Gödel (1995), with an illuminating introductory note by George Boolos. More cautious than Penrose, Gödel there comes to the conclusion that "

"There is a gap between the proposition that no finite machine meeting certain weak conditions can print a certain formal sentence (which will depend on the machine) and the statement that if the human mind is a finite machine, there exist truths that cannot be established by any proof the human mind can conceive.... it is certainly not obvious what it means to say that the human mind, or even the mind of some one human being4.8 The same appliesisa finite machine, e.g. a Turing machine. And to say that the mind (at least in its theorem-proving aspect), oramind, may be represented by a Turing machine is to leave entirely open justhowit is so represented." (Boolos (1995) p. 293).

<2>. For earlier critical discussion, see the collection Anderson (1964). For criticism in various of the peer commentaries on ENM (with responses by Penrose), see

Boolos, G. (1995). Introductory note to *1951. In Gödel (1995), pp. 290-304.

Cohen, P. (1966).

Cohen, P. (1971). Remarks on the foundations of set theory. In

Davis, M. (1993). How subtle is Gödel's theorem? More on Roger Penrose.

Feferman, S. (1962). Transfinite recursive progressions of axiomatic theories.

Feferman, S. (1988). Turing in the land of O(z). In (R. Herken, ed.)

Feferman, S. (1988a). Hilbert's program relativized: proof-theoretical and foundational reductions.

Feferman, S. (1993). Why a little bit goes a long way: Logical foundations of scientifically applicable mathematics. In

Gödel, K. (1986). Collected Works, Vol. I. Publications 1929-1936, Oxford University Press, 1986.

Gödel, K. (1990).

Gödel, K. (1995).

Kleene, S.C. (1952).

Penrose, R. (1989).

Penrose, R. (1994).

Polya, G. (1962).

Smorynski, C. (1977). The incompleteness theorems. In

Turing, A. (1939). Systems of logic based on ordinals.