Penrose's Philosophical Error

L.J.Landau

Mathematics Department
King's College London
in Concepts for Neural Networks, L.J.Landau and J.G.Taylor eds. (Springer 1997) ISBN 3-540-76163-2
This is a somewhat modified HTML version.

1.  Can Computers Think?

there must be more to human thinking than can ever be achieved by a computer. ... Consciousness, in its particular manifestation in the human quality of understanding, is doing something that mere computation cannot. I make clear that the term `computation' includes both `top-down' systems, which act according to specific well-understood algorithmic procedures, and `bottom-up' systems, which are more loosely programmed in ways that allow them to learn by experience.

Figure1: Roger Penrose, 1996. © Steve Green. Reproduced with permission.

The question at issue is not a dualistic distinction between the conscious mind and the physical brain. Penrose accepts that the conscious mind arises as a functioning of the physical brain, but he does not believe this functioning could be simulated by a large number of silicon chips operating as they do in a modern computer.

John Lucas

Gödel's theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines.

When we increase the complexity of our machines there may, perhaps, be surprises in store for us. [Turing] draws a parallel with a fission pile. Below a certain ``critical'' size, nothing much happens: but above the critical size, the sparks begin to fly. So too, perhaps, with brains and machines.... This may be so. Complexity often does introduce qualitative differences. Although it sounds implausible, it might turn out that above a certain level of complexity, a machine ceased to be predictable, even in principle, and started doing things on its own account, or, to use a very revealing phrase, it might begin to have a mind of its own. It would begin to have a mind of its own when it was no longer entirely predictable and entirely docile, but was capable of doing things which we recognized as intelligent.... But then it would cease to be a machine, within the meaning of the act.

Hilary Putnam

In 1961 John Lucas - an Oxford philosopher well known for espousing controversial views - published a paper in which he purported to show that a famous theorem of mathematical logic known as Gödel's Second Incompleteness Theorem implies that human intelligence cannot be simulated by a computer. Roger Penrose is perhaps the only well-known present-day thinker to be convinced by Lucas's argument.... The right moral to draw from Lucas's argument, according to Penrose, is that noncomputational processes do somehow go on in the brain, and we need a new kind of physics to account for them.

Shadows of the mind will be hailed as a ``controversial'' book, and it will no doubt sell very well even though it includes explanations of difficult concepts from quantum mechanics and computational science. And yet this reviewer regards its appearance as a sad episode in our current intellectual life. Roger Penrose ... is convinced by - and has produced this book as well as the earlier The emperor's new mind to defend - an argument that all experts in mathematical logic have long rejected as fallacious. The fact that the experts all reject Lucas's infamous argument counts for nothing in Penrose's eyes. He mistakenly believes that he has a philosophical disagreement with the logical community, when in fact this is a straightforward case of a mathematical fallacy.
© 1994 by The New York Times Co. Reprinted by Permission.

Kevin Warwick

I believe that in the next ten to twenty years some machines will become more intelligent than humans.

We need to go to an appropriate level of modelling the functioning of a human brain in order to obtain a very good approximation.... Is it down, much further than the neuron level, to the atomic level? Should we look at quantum physics... as Penrose thinks, generating an atomic model of the brain's functioning that we do not yet have?... In reality I feel that we already do have sufficient basic modelling blocks.... What are those blocks? They are the neurons, the fundamental cells in the brain which cause it to operate as it does.

One major problem with consciousness is that it is a state which we ourselves feel that we are in, and through this we are aware of ourselves. It can, therefore, be extremely difficult, when thinking about ourselves, to realise that this is simply a result of a specific state of the neurons in our brain. These `private' thoughts and feelings we have, how can they possibly be simply a state of mind, realised by a state of the neurons? Well, that is exactly what they are.

Alan Turing

Figure2: Alan Turing, 1951. By courtesy of the National Portrait Gallery, London.

Since part of Penrose's argument is based on a theorem of Turing concerning a limitation on what can be achieved by computers, it is interesting to know Turing's thoughts on these issues. Turing wrote an article [24]⁴ in which he gives his opinion on whether or not a computer will ever be able to think. In the article Turing states his belief that his own fundamental theorem concerning the limitations of computing machines is not an obstacle to the creation of intelligent computers.

Turing begins his article with the sentence:

I propose to consider the question, `Can machines think?'

Turing states clearly that he believes the computer will do well at imitating human behavior and gives 50 years as the time scale when computers will have become sufficiently powerful to begin doing this. He was writing in 1950 and so we are just coming to his predicted time period. (Remember the new Sandia-Intel supercomputer!) About his beliefs he says:

I believe further that no useful purpose is served by concealing these beliefs. The popular view that scientists proceed inexorably from well-established fact to well-established fact, never being influenced by any unproved conjecture, is quite mistaken. Provided it is made clear which are proved facts and which are conjectures, no harm can result. Conjectures are of great importance since they suggest useful lines of research.

Instead of trying to produce a programme to simulate the adult mind, why not rather try to produce one which simulates the child's? If this were then subjected to an appropriate course of education one would obtain the adult brain.... Our hope is that there is so little mechanism in the child-brain that something like it can be easily programmed. The amount of work in the education we can assume, as a first approximation, to be much the same as for the human child.

There are a number of results of mathematical logic which can be used to show that there are limitations to the powers of discrete-state machines. The best known of these results is known as Gödel's theorem, and shows that in any sufficiently powerful logical system statements can be formulated which can neither be proved nor disproved within the system, unless possibly the system itself is inconsistent. There are other, in some respects similar, results due to Church, Kleene, Rosser, and Turing. The latter result is the most convenient to consider, since it refers directly to machines, whereas the others can only be used in a comparatively indirect argument: for instance if Gödel's theorem is to be used we need in addition to have some means of describing logical systems in terms of machines, and machines in terms of logical systems. The result in question refers to a type of machine which is essentially a digital computer with an infinite capacity. It states that there are certain things that such a machine cannot do. If it is rigged up to give answers to questions as in the imitation game, there will be some questions to which it will either give a wrong answer, or fail to give an answer at all however much time is allowed for a reply. There may, of course, be many such questions, and questions which cannot be answered by one machine may be satisfactorily answered by another. We are of course supposing for the present that the questions are of the kind to which an answer `Yes' or `No' is appropriate, rather than questions such as `What do you think of Picasso?' The questions that we know the machines must fail on are of this type, ``Consider the machine specified as follows... Will this machine ever answer `Yes' to any question?'' The dots are to be replaced by a description of some machine in a standard form, which could be something like that used in 5. When the machine described bears a certain comparatively simple relation to the machine which is under interrogation, it can be shown that the answer is either wrong or not forthcoming. This is the mathematical result: it is argued that it proves a disability of machines to which the human intellect is not subject.

The short answer to this argument is that although it is established that there are limitations to the powers of any particular machine, it has only been stated, without any sort of proof, that no such limitations apply to the human intellect. But I do not think this view can be dismissed quite so lightly. Whenever one of these machines is asked the appropriate critical question, and gives a definite answer, we know that this answer must be wrong, and this gives us a certain feeling of superiority. Is this feeling illusory? It is no doubt quite genuine, but I do not think too much importance should be attached to it. We too often give wrong answers to questions ourselves to be justified in being very pleased at such evidence of the fallibility on the part of the machines. Further, our superiority can only be felt on such an occasion in relation to the one machine over which we have scored our petty triumph. There would be no question of triumphing simultaneously over all machines. In short, then, there might be men cleverer than any given machine, but then again there might be other machines cleverer again, and so on.

We may hope that machines will eventually compete with men in all purely intellectual fields. But which are the best ones to start with? Even this is a difficult decision. Many people think that a very abstract activity, like the playing of chess⁶, would be best. It can also be maintained that it is best to provide the machine with the best sense organs that money can buy, and then teach it to understand and speak English. This process could follow the normal teaching of a child. Things would be pointed out and named, etc. Again I do not know what the right answer is, but I think both approaches should be tried.

We can only see a short distance ahead, but we can see plenty there that needs to be done.

Penrose's Error

One answer to this question might be that I am unable - because of my intellectual limitations, interests in other matters, general laziness, or some combination of all three - to follow Penrose's arguments through their many details. Perhaps he is right, and I just don't get it.

But let us begin by discussing the basic mathematical results, unencumbered by possible applications to a theory of mind.

2.  Solving Problems in Arithmetic

27+96=?

In order to solve problems in arithmetic (which for concreteness we will take to mean questions about quantities of marbles) we must first agree on a certain set of basic instructions, or operations on the marbles, from which a rule may be given to perform more complicated operations. The rule is a program to be executed by performing the basic instructions one after the other. We might ask questions about the result of executing a program starting from some initial collection of bowls with marbles in them. If the program represents addition then we are asking a question about addition. If the program represents multiplication then we are asking a multiplication question. And so on.

Why do we choose to formulate arithmetic in terms of bowls of marbles? Because in this way arithmetic corresponds to concrete actions on concrete objects (marbles, or coins, etc.). This is how arithmetic originally developed, as a concrete activity rather than an abstract mental construct. At this stage there is no logic, no deduction or proof, just concrete actions carried out according to instructions which define addition, multiplication, and other more complicated arithmetical procedures. At a later stage we may reason about these arithmetical procedures, using rules of deduction which seem to us to be sound.

The Basic Instructions

Zero instructions.

For each k = 0,1,2,¼ there is a zero instruction Z(k). The meaning of the instruction Z(k) is to change the content r_k of the register R_k to 0, leaving all other registers unaltered. Thus, to carry out the instruction Z(k) simply empty the k^th bowl.

Successor instructions.

For each k = 0,1,2,¼ there is a successor instruction S(k). The meaning of the instruction S(k) is to change the content r_k of the register R_k to r_k+1, leaving all other registers unaltered. Thus to carry out the instruction S(k) simply add a marble to the k^th bowl.

Transfer instructions.

For each j = 0,1,2,¼ and k = 0,1,2,¼ there is a transfer instruction T(j,k). The meaning of the instruction T(j,k) is to replace the content r_k of the register R_k with the number r_j contained in R_j, leaving all other registers unaltered. Thus to carry out the instruction T(j,k) take a spare bowl and put into it a quantity of marbles equal to the quantity of marbles in the j^th bowl. Then replace the marbles in the k^th bowl with the marbles in the spare bowl.

Jump instructions.

The preceding three instructions are called arithmetical instructions, and they manipulate the quantity of marbles contained in the bowls. The final type of instruction is of a different sort and determines how you process the program. For each j = 0,1,2,¼, k = 0,1,2,¼, and l = 0,1,2,¼ there is a jump instruction J(j,k,l). The meaning of the instruction J(j,k,l) is as follows⁸:

1. if r_j = r_k proceed to the l^th instruction in the program
2. if r_j ¹ r_k proceed to the next instruction in the program

None of the contents of the registers is altered by a jump instruction.

The setup we have been considering, consisting of registers (bowls) R_k containing numbers (of marbles) r_k and programs of instructions of the previously discussed type, is called an Unlimited Register Machine or URM for short.¹⁰ Using this approach you can compute any function which can be computed in any other way. In particular, you can compute the same functions as Turing machines compute.

A program P has a finite specification by the instructions I₀,¼,I_b. You can however execute the program with infinitely many possible initializations of the registers. The program thus represents a uniform way for you to deal with the infinitely many cases you may be presented with.

Comment

A Sample Program

Another Sample Program

Numbering All Programs

Zero instructions.

Assign numbers to the zero instructions by associating the instruction Z(k) with the number k.

Successor instructions.

Assign numbers to the successor instructions by associating the instruction S(k) with the number k.

Transfer instructions.

In order to assign numbers to the transfer instructions we must be able to encode pairs of numbers (j,k) by a single number. We associate¹⁴ the pair of numbers (j,k) with the number n = f(j,k) = 2^j(2k+1)-1. Conversely, we can find j and k from n by j = f₁(n), k = f₂(n) where f₁(n) is the largest power j such that 2^j divides n+1, and:

f2(n) = 1 2 é ê ë n+1 2f1(n) -1 ù ú û

Then the transfer instruction T(j,k) is associated with the number n = f(j,k).

Jump instructions.

In order to assign numbers to the jump instructions we must be able to encode triples of numbers (j,k,l) by a single number. In fact, once we have encoded pairs of numbers, we can encode triples, quadruples, etc. We associate to the triple of numbers (j,k,l) the number m = g(j,k,l) = f(f(j,k),l). From m we can find j,k,l by l = f₂(m), j = f₁(f₁(m)), and k = f₂(f₁(m)).

Then the jump instruction J(j,k,l) is associated with the number m = g(j,k,l).

Zero instructions.

The zero instruction Z(k) is associated with the number 4k.

Successor instructions.

The successor instruction S(k) is associated with the number 4k+1.

Transfer instructions.

The transfer instruction T(j,k) is associated with the number 4f(j,k)+2.

Jump instructions.

The jump instruction J(j,k,l) is associated with the number 4g(j,k,l)+3.

In the final step we assign numbers to the programs P = I₀,I₁,¼,I_b. Since we have assigned numbers to the individual instructions, we can associate with P the sequence of numbers m₀,m₁,¼,m_b, where m_j is the number assigned to the instruction I_j. Thus we must encode all such sequences of numbers into a single number. One way to do this is to associate to the numbers m₀,m₁,¼,m_b the number:

We may explain formula (4) this way. Given the program P and the corresponding Gödel numbers m₀,m₁,¼,m_b we compute h using the following prescription:

Computing Gödel Numbers

Let's find the programs corresponding to some Gödel numbers:

1. The program with Gödel number 0: Since 0 = 2⁰-1 we see from (2) that b = 0 and m₀ = 0. Thus the program has only one instruction and that instruction has number 0. The zero instruction Z(k) has the number 4k, hence the instruction Z(0) has number 0. In conclusion, the program with Gödel number 0 is P₀ = Z(0). What would you accomplish by executing the program P₀? Simply empty the bowl R₀.
2. The program with Gödel number 1: Since 1 = 2¹-1 we see from (2) that b = 0 and m₀ = 1. The successor instruction S(k) has the number 4k+1, hence the instruction S(0) has number 1. In conclusion, the program with Gödel number 1 is P₁ = S(0). What would you accomplish by executing the program P₁? Simply add a marble to bowl R₀.
3. The program with Gödel number 2: Since 2 = 2⁰+2¹-1 we see from (2) that b = 1 and m₀ = 0,m₁ = 0. Then P₂ = Z(0),Z(0). You will obtain precisely the same result by executing P₂ or P₀ (but you empty bowl R₀ twice!).
4. The program with Gödel number 7: Since 7 = 2³-1 we see that b = 0 and m₀ = 3. Thus the program consists of only one instruction and that instruction has number 3. This is the jump instruction J(0,0,0). So P₇ = J(0,0,0). If you execute this program you will never halt. You will keep repeating the first instruction (which is to perform the first instruction) but you will make no change to the contents of the registers!

Zero instructions.

Since the Gödel number of Z(k) is 4k, the Gödel number of Z(1) is 4 and the Gödel number of Z(2) is 8.

Successor instructions.

Since the Gödel number of S(k) is 4k+1, the Gödel number of S(0) is 1 and the Gödel number of S(2) is 9.

Jump instructions.

Since the Gödel number of J(j,k,l) is

4g(j,k,l)+3 = 4f(f(j,k),l)+3  ,

we compute the Gödel number of J(0,0,0) as 4f(f(0,0),0)+3. Since f(0,0) = 2⁰(2·0+1)-1 = 0, we get 4f(0,0)+3 = 4·0+3 = 3. So the Gödel number of J(0,0,0) is 3. Similarly, the Gödel number of J(2,1,4) is 4g(2,1,4)+3 = 4f(f(2,1),4)+3. Now f(2,1) = 11, so g(2,1,4) = f(f(2,1),4) = 2¹¹·9-1 = 2048·9-1 = 18431. So the Gödel number of J(2,1,4) is 73727.

The Marrakech Game

This is a magic square, where the numbers add to 15 along any row, column, or diagonal.

The first player begins the game by putting an X in one of the squares on the board. This is the same as choosing a number from 1 to 9. The second player now puts an O in one of the remaining squares. This is the same as choosing one of the remaining numbers. Play proceeds like this until one player has marked all the squares in a row, column, or diagonal. This is the same as one player having three numbers which add to 15.

We have thus reformulated the game of tic-tac-toe as an equivalent game involving a purely numerical procedure of choosing numbers from 1 to 9, the game being won when a player gets three numbers which add to 15. It is described in Karl Fulves' Self-Working Number Magic [9] where it is called the marrakech game.

Of course, as numbers do not carry any meaning beyond their place in the succession of numbers, the marrakech game no longer has the same `meaning' as the original game. (The marrakech game is harder to play than tic-tac-toe because the geometrical symmetries of the tic-tac-toe board and the geometry of the game play are not present in the marrakech game.)

3.  The Barber Paradox

We have seen that all programs can be numbered: P₀,P₁,P₂,¼. Let's say that a number m is produced by a program P_n if there is an initial value r₀ of register R₀ such that when all other registers are initialized to 0 (r_k = 0 for k ¹ 0) and the program executed, the program will be completed with m in register R₀ (and any numbers in the other registers). We will be interested in the family of statements S_n of the form `n is not produced by P_n'. Which statements S_n can be shown to be true? For some values of n, by reasoning about the sequence of instructions in P_n you might find a way of demonstrating that S_n is true. For other values of n you might be able to demonstrate that S_n is false. For still other values of n you might have no idea whether or not S_n is true (or even whether or not it is meaningful to ask if it is true). For example:

1. The program P₀ = Z(0). Hence no matter what the value r₀ initially in register R₀ this program will be completed after one step and the content of register R₀ will be 0. Thus 0 is the only number produced by P₀. Since 0 is produced by P₀ the statement S₀ is false.
2. The program P₁ = S(0). Hence if r₀ is initially in register R₀ this program will be completed after one step and the content of register R₀ will be r₀+1. Thus all the numbers 1,2,3,¼ will be produced by P₁. Since 1 is produced by P₁ the statement S₁ is false.
3. The program P₂ = Z(0),Z(0). This program produces only the number 0. Since 2 is not produced by P₂, the statement S₂ is true.
4. Let a be the number 2⁷³⁷²⁷+2⁷³⁷²⁹+2⁷³⁷³⁹+2⁷³⁷⁴³+2⁷³⁷⁴⁸+2⁷³⁷⁵⁷-1. Then P_a is the program (1) which adds any two numbers. Hence if we set r₀ to any initial value and all other registers to 0 (in particular r₁ = 0) then the result of executing P_a will be r₀+r₁ = r₀ in register R₀. Thus P_a produces all numbers. Since a is produced by P_a, the statement S_a is false.

To see that no such P_l exists, suppose P_l produces the number l. Then, given that P_l is sound, it follows that S_l is true, i.e. P_l does not produce l. This contradiction means that a sound program cannot produce its own Gödel number. Thus, given that P_l is sound, it follows that P_l does not produce l. Therefore S_l is true. Hence the sound program P_l cannot produce the number l of the true statement S_l. Hence we have our first main result:

Figure5: Flow diagram for the program P_l^¢ .

The registers are initialized to 0 except R₀ which is set to r₀ = m. First test if m = 0 by comparing r₀ and r₁ (since r₁ = 0). If m = 0, add¹⁵ l to r₀ and halt. If m ¹ 0, subtract¹⁶ 1 from r₀ and then execute the program P_l.

Consequently the program P_l^¢ is also sound and furthermore produces the number l, a number not produced by P_l. But the previous argument applied to P_l^¢ shows that S_l^¢ is true but not produced by P_l^¢ (and hence also not by P_l). This is our third main result:

Comment

4.  Gödel's Theorem

Figure6: Kurt Gödel, 1939. Reproduced by permission of the Institute for Advanced Study, Princeton, USA

In section 2 we defined the basic instructions and the programs composed of these instructions. I can explain to you very simply what you are to do when following each instruction and you may then execute the program. It is all very concrete and involves moving marbles in a specific way. A chimpanzee could be trained to execute some programs. A mechanical contraption could be built which would execute the programs, depending on how various levers were set. A present-day computer could be set up to execute any program if you type the instructions on the keyboard. There is no `logic' or reasoning which forms part of the process of executing a program. On the other hand, in section 3 we have been reasoning about programs. This involves something different from the programs themselves. What constitutes valid reasoning? Can we be absolutely precise as to what shall consistute an acceptable proof? In what language shall the reasoning take place?¹⁷ It was with the objective in mind of setting down a precise, consistent framework in which to conduct mathematical reasoning that formal mathematical systems were developed. A formal mathematical system is formulated with a specified language, which consists of an alphabet of symbols, together with rules for writing down formulas. In addition, there are rules¹⁸ which determine when a finite sequence of formulas constitutes a proof, the final formula of the proof being the theorem which is proved. The most characteristic property of such systems is the mechanical nature of proof-checking, a property emphasized by David Hilbert (1862-1943). Let's decide on a method¹⁹2 to encode formulas and finite sequences of formulas into (Gödel) numbers. Then the mechanical nature of proof-checking means that there is a program P_l which will produce precisely the Gödel numbers of proofs, and a program P_m which will produce the Gödel numbers of the last formula in each proof. Every proof will eventually be produced by P_l and hence every theorem will eventually be produced by P_m.

When we use a formal mathematical system we have a particular interpretation in mind for the symbols and formulas. However, someone else may use the same formal system with a different interpretation.²⁰ The formal system gives rules for writing symbols on paper. It has no intrinsic meaning and does not come with an interpretation. For this reason, Bertrand Russell once said (quoted in chapter XI of [12]):

Mathematics may be defined as the subject in which we never know what we are talking about nor whether what we are saying is true.

Mathematics is the art of giving the same name to different things.

So suppose we have settled on a particular formal system to make deductions about the programs we have been considering. We interpret²² the formulas as statements about programs. The statement S_n, discussed in the preceding section, will be expressed by a formula f_n. Then if S_n is true we will say that the formula f_n is true, and if S_n is false we will say that the formula f_n is false.

From the program P_m which produces the Gödel numbers of all the theorems of the formal system, we can write down a program P_j which produces the number n if and only if f_n is a theorem. Here's a prescription to do this. For given input, execute P_m. If P_m halts and produces the number k, then we know k is the Gödel number of a theorem. To find out if k corresponds to one of the formulas f_n, we need to use the program P_M which, given input n, produces the Gödel number of f_n. We execute P_M repeatedly with input 0, then 1, then 2, etc. comparing the number produced with k. If k is not the Gödel number of some f_n the program will not halt. If k is the Gödel number of f_n then the program produces n as output. This prescription in words must be translated into a program P_j. This is easy to do once we have the programs P_m and P_M. A flow diagram for P_j is shown²³7 in Figure 7. Summarizing, from the program P_m which produces the Gödel numbers of theorems of our formal system, and the program P_M which from input n produces the Gödel number of f_n, we can write down a program P_j which produces the numbers n such that f_n is a theorem.

Figure7: Flow diagram for the program P_j.

Let us now suppose that our formal system is sound, i.e. the theorems are true. Thus P_m will produce only Gödel numbers of true formulas, and hence P_j will produce only numbers n such that S_n is true. Thus P_j is sound. It follows by (5) that the number j is not produced by P_j and S_j is true. Thus f_j is true and not produced by P_m, i.e. f_j is true but is not a theorem of the formal system. This conclusion holds for any sound formal mathematical system with a language sufficiently broad to express the statements S_n. We thus have the following version of Gödel's theorem:

How to Understand Gödel's Theorem

1. We can explicitly exhibit a formula f_j which is not a theorem of the formal system but is nevertheless true in our interpretation. However in another interpretation f_j will be false.²⁴

   An interpretation gives meaning to the formal system and this meaning leads us to truths not derivable from the formal system itself. This must be expected if a formal system can be given different interpretations, and so different meanings and truths.

2. Gödel's theorem says that we cannot deduce as theorems all true formulas, from the limited set of true formulas which constitute the axioms. The axioms constitute a set of truths of limited complexity and we cannot expect to derive truths of unlimited complexity from them. Chaitin (see [5]) puts it this way: The complexity of the formal system ¼ is a measure of the amount of information the system contains, and hence the amount of information that can be derived from it. ¼ Gödel's theorem does not appear to give cause for depression. Instead it seems simply to suggest that in order to progress, mathematicians, like investigators in other sciences, must search for new axioms.

   If one has ten pounds of axioms and a twenty pound theorem, then that theorem cannot be derived from those axioms.

3. Using a formal system to deduce theorems (which are truths if the formal system is sound), you are acting as an oracle producing statements. Gödel's theorem describes a limitation which applies not only to computational oracles (programs or formal systems) but to any oracle, regardless of its nature. An oracle which is known to be sound can never tell us everything we can ascertain. Thus the Gödel phenomenon cannot be overcome by searching for a non-computational oracle. We will show how this limitation arises by analogy with our previous discussion.

   An oracle in the form of a `black box', the interior of which we do not know, produces statements. The oracle is sound if all the statements are true. Now define²⁵ a device D which does the following: if the oracle produces the statement D does not produce anything, then D produces the number 0 in response. If the oracle produces any other statement, D does not produce anything in response.

   We may easily deduce that if the oracle is sound, then it will not produce the statement D does not produce anything, and furthermore it is true that D does not produce anything. Thus if we know the oracle is sound, then we know a truth not produced by the oracle.

5.  Penrose

I am reminded of a story concerning the great American physicist Richard Feynman. Apparently Feynman was explaining some idea to a student, but mis-stated it. When the student expressed puzzlement, Feynman replied: `Don't listen to what I say; listen to what I mean!'

I shall shortly be giving (in Chapters 2 and 3) some very strong reasons for believing that effects of (certain kinds of) understanding cannot be properly simulated in any kind of computational terms... Thus, the human faculty of being able to `understand' is something that must be achieved by some non-computational activity of the brain or mind... The term `non-computational' here refers to something beyond any kind of effective simulation by means of any computer based on the logical principles that underlie all the electronic or mechanical calculating devices of today.

The argument I shall present in the next chapter (section 2.5) provides what I believe to be a very clear-cut argument for a non-computational ingredient in our conscious thinking... In due course (in Chapters 2 and 3), I shall be addressing, in detail, all the different counter-arguments that have come to my attention.

The Gödelian Case

What Penrose has shown is quite compatible with the claim that a computer program could in principle successfully simulate our mathematical capacities. The possibility exists that each of the rules that a human mathematician explicitly relies on, or can be rationally persuaded to rely on, can be known to be sound and that the program generates all and only these rules but that the program itself cannot be rendered sufficiently ``perspicuous'' for us to know that that is what it does. Actual programs sometimes consist of thousands of lines of code, and it can happen that by the time a program has been tinkered with and debugged no one is really able to explain exactly how it works. A program which simulated the brain of an idealized mathematician might well consist of hundreds of thousands (or millions or billions) of lines of code. Imagine it given in the form of a volume the size of the New York telephone book. Then we might not be able to appreciate it in a perfectly conscious way, in the sense of understanding it or of being able to say whether it is plausible or implausible that it should output correct mathematical proofs and only correct mathematical proofs.
© 1994 by The New York Times Co. Reprinted by permission.

Do Mathematicians Use Unsound Reasoning?

I cannot really see that it is plausible that mathematicians are really using an unsound formal system F as the basis of their mathematical understandings and beliefs. I hope the reader will indeed agree with me that whether or not such a consideration is possible, it is certainly not at all plausible.

I have told the story of this controversy in such detail, because I think that it constitutes the best caution against taking the immovable rigour of mathematics too much for granted. This happened in our own lifetime, and I know myself how humiliatingly easy my own views regarding the absolute mathematical truth changed during this episode, and how they changed three times in succession!... It is hardly possible to believe in the existence of an absolute, immutable concept of mathematical rigor, dissociated from all human experience.

John von Neumann (from [26])

Mathematics may be likened to a Promethean labor, full of life, energy and great wonder, yet containing the seed of an overwhelming self-doubt. It is good that only rarely do we pause to review the situation and to set down our thoughts on these deepest questions. During the rest of our mathematical lives we watch and perhaps partake in the glorious procession.... This is our fate, to live with doubts, to pursue a subject whose absoluteness we are not certain of, in short to realize that the only ``true'' science is itself of the same mortal, perhaps empirical, nature as all other human undertakings.

Paul J. Cohen (from [6])

I wanted certainty in the kind of way in which people want religious faith. I thought that certainty is more likely to be found in mathematics than elsewhere. But I discovered that many mathematical demonstrations, which my teachers expected me to accept, were full of fallacies, and that, if certainty were indeed discoverable in mathematics, it would be in a new field of mathematics, with more solid foundations than those that had hitherto been thought secure.... After some twenty years of very arduous toil, I came to the conclusion that there was nothing more that I could do in the way of making mathematical knowledge indubitable.[19]... The splendid certainty which I had always hoped to find in mathematics was lost in a bewildering maze.[20]

Bertrand Russell

Only he who recognizes that he has nothing, that he cannot possess anything, that absolute certainty is unattainable, who completely resigns himself and sacrifices all, who gives everything, who does not know anything, does not want anything and does not want to know anything, who abandons and neglects everything, he will receive all; to him the world of freedom opens, the world of painless contemplation and of - nothing.

L.E.J.Brouwer (from [3])

Unassailable Mathematical Beliefs

6.  A Computational Model for Thought?

1. Decide on which aspects of the phenomenon are to be modelled: in the case of the projectile, the position of the projectile at various moments of time.
2. Set up measuring instruments to code those aspects of the phenomenon into numerical quantities. (The meter readings serve as `Gödel numbers' which code those aspects of the phenomenon into numbers.) In the case of the projectile, we set up rulers and clocks.
3. Set up a mathematical theory (in this case, based on Newton's Laws of Motion) to compute relationships between the instrument readings. In the case of the projectile, write a program such that with the registers appropriately initialized, the program is completed with the register R₀ containing a number which should, if the computational model is a good one, be very close to the number obtained by reading the ruler.

1. The functioning of the brain is described by the connections between neurons. The state of the brain at any time is described by the state of firing or non-firing of each of the neurons.
2. A mathematical model of the brain is constructed by associating with the j^th neuron a mathematical variable f_j(t) which takes the value 0 or 1, describing the state of the neuron at time t (the time being measured in discrete steps). The value 1 corresponds to the neuron firing, and the value 0 to non-firing. The configuration of all the neurons at a given time is thus modelled by all the values f₀(t),f₁(t),¼,f_N(t). The values f₀(t+1),f₁(t+1),¼,f_N(t+1) are determined by the values f₀(t),f₁(t),¼,f_N(t) together with a computational rule which models the dynamical behaviour of the neural network. That is, we give a mathematical rule which enables us to calculate each f_j(t+1) given all the values f₀(t),¼,f_N(t). One such rule is described in Chapters 1 and 2, in terms of weights which correspond to neural connections. The weights w_ji are introduced, which take positive or negative integer values²⁸, and model the strength of the connection from the i^th neuron to the j^th neuron. Then the computational rule governing the behavior of the mathematical model is:

   fj(t+1) = ì ï í ï î 1   if   wj1f1(t)+¼+wjNfN(t) > Mj 0   if   wj1f1(t)+¼+wjNfN(t) £ Mj

   (13)

   where M_j is a positive integer corresponding to the threshold of the j^th neuron.
   Remark. External input can be incorporated into the model by `plugging in by hand' the values f_j(t) corresponding to the sensory neurons.
3. The preceding computational rule may be expressed²⁹ by a program P_l. The program will be constructed so that by executing the program we perform the computations expressed in (11). We initialize the registers with r_j = f_j(t) (all others initialized to 0) and execute the program P_l. When we complete the program the registers will contain r_j^¢ = f_j(t+1), for j = 0,¼,N.

   In this way by executing the program P_l we may compute the values f₀(t),¼,f_N(t) for all (discrete) times t, and consequently the sequence of states of the neural network.

A Computational Model for the Mind?

What are we to make of the popular notion that our brains are somehow libraries of our thoughts and beliefs? Is it in principle possible that brain scientists might one day know enough about the workings of our brains to be able to ``crack the cerebral code'' and read our minds?

Hence to compute the beliefs held by a brain at time t initialize the registers to r_k = f_k(0), k = 0,¼,N. Then execute the program P_l. When you complete the program you will have r_k^¢ = f_k(1) in the registers. Continue these computations until you have obtained f₀(t),¼,f_N(t). Now execute the dictionary program P_d with the registers initialized to r_k = f_k(t). When you complete the program P_d you will obtain a number b(t) which encodes all the beliefs held by the brain at time t. The number b(t) could be decoded to yield all the beliefs B₀(t),¼B_N(t) at time t stated in English. Combining the above steps, we can write a program P so that, initializing the registers to f₀(0),¼,f_N(0),t, then upon completing the program P the Gödel belief number b(t) will be in the register R₀.

Gödel's Objection?

Experience has taught most mathematicians that much that looks solid and satisfactory to one mathematical generation stands a fair chance of dissolving into cobwebs under the steadier scrutiny of the next... Knowledge in any sense of a reasonably common agreement on the fundamentals of mathematics seems to be non-existent... The bald exhibition of the facts should suffice to establish the one point of human significance, namely, that equally competent experts have disagreed and do now disagree on the simplest aspects of any reasoning which makes the slightest claim, implicit or explicit, to universality, generality, or cogency.

The Mistaken Application of Gödel's Theorem

Suppose a human, who we call H, has a computational mind (associated with the program P), and that H is made aware of the program P which we are using to compute the properties of his brain. We may use a formal mathematical system F to logically deduce the behavior of P, and hence the behavior, beliefs, and other thoughts of H. We may say that the system F encapsulates all the knowledge and beliefs of H. Penrose argues that if H believes statement X, then since F encapsulates all of H's beliefs, it must be possible to prove X in the system F. Penrose then reasons that H will surely believe that the system F is sound. Consequently, H will believe (by Gödel's theorem) that the formula f is true. But since, again by Gödel's theorem, f is not a theorem of F, it follows that F cannot after all encapsulate all of H's beliefs.³² By this contradiction Penrose concludes that H cannot in fact have a computational mind.

Penrose's confusion in this line of reasoning is italicized above. For if H believes X (on day 1) then it is necessary that F deduces that H believes X on day 1. It is not necessary that F deduces X. If on day 2 H changes his mind and believes the negation of X, ØX, then it is necessary that F deduces that H believes ØX on day 2. It is not necessary that F deduces ØX. If on day 3 H goes crazy then it is necessary that F deduces that H is crazy on day 3. It is not necessary that F deduces all sorts of crazy formulas.

In short, although F cannot deduce f, there is no reason why F cannot deduce that H believes f. Gödel's theorem doesn't say anything about what can be proved concerning the state of H's mind!

The essential point is that H's beliefs do not form part of the deductive system F. If H believes two contradictory statements X and Y, these statements are not theorems of F and so it does not follow that F is inconsistent, as it would be if X and Y were theorems.³³

Let's explain in detail the distinction between X and H believes X, using our `toy' computational model. The statement X is one of H's beliefs, say B<sub>k</sub>(t), and as such is encoded along with H's other beliefs in the Gödel belief number b(t). Using the formal system F we can deduce a theorem which states that when the program P is run with registers initialized to r<sub>k</sub> = f<sub>k</sub>(0) then when the program is completed r<sub>0</sub> = b(t). There is a world of difference between the theorem r<sub>0</sub> = b(t) and the statements B<sub>0</sub>(t),¼,B<sub>N</sub>(t) encoded in the number b(t). The confusion undoubtedly arose because the mathematical beliefs of H could be expressed in the same language used in the formal system F. No one would think of incorporating a non-mathematical belief, such as `It will rain tomorrow', into the formal system F !

Discussion

Consider a present day computer. What sort of expressions might it print out? Consider the formal system F associated with the program it is running. Suppose the formula f is not provable in F. Is there any reason why the formula f cannot be printed out by the computer? No! Again, what comes out of the printer is not a theorem of F.

All this becomes clear when it is realized that what is printed out, or drawn, etc., need not satisfy any grammatical rules, which are required of theorems of F.

Related Ideas in the Literature

6.0.1 John von Neumann

When we talk mathematics, we may be discussing a secondary language, built on the primary language truly used by the central nervous system. Thus the outward forms of our mathematics are not absolutely relevant from the point of view of evaluating what the mathematical or logical language truly used by the central nervous system is. However, the above remarks about reliability and logical and arithmetical depth prove that whatever the system is, it cannot fail to differ considerably from what we consciously and explicitly consider as mathematics.

Robert Kirk

If there could be adequate mechanistic accounts which represented a person by means of a formal system, yet did not correlate beliefs, thoughts or statements with that system's theorems or `outputs', then the argument from Gödel fails. In fact, there is an approach which appears to satisfy this requirement. It deals in terms of the organism's physical states, inputs, and outputs, all at some rather low level of specification - perhaps the neurophysiological - and in possible transitions from state to state through time.... Certainly mechanists will maintain that those tokens of mathematical sentences which Alf produces are produced `mechanically'. However, in maintaining this they need not - and should not - say that the token sentences themselves correspond to theorems of a formal system which adequately represents Alf and his part of the world.

7.  Can Computers Think?

Will computers of the future be intelligent?

Supercomputers will some day soon start competing with mathematicians and may well put them forever out of work.... Of course, present-day machines are useful mostly for rather repetitious and somewhat stupid tasks. But there is no reason why they could not become more flexible and versatile, mimicking the intellectual processes of man, with tremendously greater speed and accuracy. In this way, within fifty or a hundred years (or maybe two hundred), not only will computers help mathematicians with their work, but we shall see them take the initiative, introduce new and fruitful definitions, make conjectures, and then obtain proofs of theorems far beyond human intellectual capabilities.
© 1991 by Princeton University Press. Reprinted with permission.

Some Thoughts about Thinking

It is never to the point in computer simulation that one's model be indistinguishable from the modelled. Consider, for instance, a good computer simulation of a hurricane, as might be devised by meteorologists. One would not expect to get wet or wind-blown in its presence. That ludicrous expectation would be akin to a use-mention error, like cowering before the word ``lion''.

No one would suppose that we could produce milk and sugar by running a computer simulation of the formal sequences in lactation and photosynthesis, but where the mind is concerned many people are willing to believe in such a miracle because of a deep and abiding dualism: the mind they suppose is a matter of formal processes and is independent of quite specific material causes in the way that milk and sugar are not.

How to Build a Robot

• eyes made of video cameras
• ears made of microphones
• a speaker for a voice box
• chemical sensors for a nose
• mechanical legs for moving about
• mechanical arms for touching and moving things

To make the brain, we'll use the URM. Take all the bowls and marbles, and your program P_l which defines a good computational model of some particular brain, and sit down inside the robot. Now suppose that when certain bowls have a marble in them (modelling an excited neuron) an action is performed by the robot (a small arm movement, for example). Suppose also that input from the video cameras (or microphones, etc.) leads to certain other bowls having a marble dropped in them (corresponding to the excitation of sensory neurons). You now execute the program P_l. Then, during each time step t® t+1, the marbles in the bowls change (modelling the varying excitation states of the neurons in the brain) causing the robot to react to external stimuli, to speak through the speaker, and so on. Of course, you must imagine yourself working faster and faster, and the bowls of marbles very small. In this way, the collection of bowls of marbles with you executing the program P_l becomes the brain of the robot.

The Mind Demon

Among the bowls are `input bowls' whose contents reflect properties of the outside world, and `output bowls' whose contents determine actions by the robot.

The sequence of bowl contents r_j(t) at times t = 0,1,2,¼, for j = 0,¼,N corresponds to the sequence of neuron firings of the j^th neuron in the brain which is modelled by the program P_l. The program P_l corresponds to the connectivity of the neural network (through the weights w_ij). The demon, executing the program P_l, corresponds to the electro-chemical forces which induce the temporal development of the neural network (its varying neuronal firings).

Question. You know that you think³⁶; how close does this robot come to doing the same?

Searle's Chinese Room

Whatever purely formal principles you put into the computer, they will not be sufficient for understanding, since a human will be able to follow the formal principles without understanding anything.... I will argue that in the literal sense the programmed computer understands what the car and the adding machine understand, namely, exactly nothing. The computer understanding is not just (like my understanding of German) partial or incomplete; it is zero.

Imagine the robot in China, and the program P_l giving a good computational model of the brain of some Chinese person. The robot will function in China in the same way that the Chinese person does. It will make replies, in Chinese, to questions asked of it by Chinese people. Searle imagines himself taking the part of the demon. He then compares his excellent understanding of English with his total lack of understanding of Chinese, and concludes that also the robot could not `understand' Chinese. But again, the demon, or Searle-in-the-robot, is not where understanding is expected to reside. Searle's reference to the understanding of English which Searle-in-the-robot possesses involves a category-mistake, as pointed out by Margaret Boden [1]:

Searle's description of the robot's pseudo-brain (that is, of Searle-in-the-robot) as understanding English involves a category-mistake comparable to treating the brain as the bearer - as opposed to the causal basis - of intelligence.

The `Feel' of Thinking

The problem with the brain simulator is that it is simulating the wrong things about the brain. As long as it simulates only the formal structure of the sequence of neurone firings at the synapses, it won't have simulated what matters about the brain, namely its causal properties, its ability to produce intentional states.

I am quite prepared to talk of the spiritual life of an electronic computer; to say that it is considering or that it is in a bad mood. What really matters is the unambiguous description of its behaviour, which is what we observe. The question as to whether the machine really feels, or whether it merely looks as though it did, is absolutely as meaningless as to ask whether light is ``in reality'' waves or particles. We must never forget that ``reality'' too is a human word just like ``wave'' or ``consciousness.'' Our task is to learn to use these words correctly - that is, unambiguously and consistently.

References

[1]

M.A. Boden, Escaping from the Chinese Room, in The Philosophy of Artificial Intelligence, ed. M.A. Boden, (Oxford University Press, 1990), pp.40-66

[2]

L. Boltzmann and B. McGuinness, Theoretical Physics and Philosophical Problems, vol.5 (D. Reidel Publishing Company, 1974) p.57

[3]

L.E.J. Brouwer, Life, Art and Mysticism 1905 exerpts; in Collected Works 1, ed. A. Heyting, (North-Holland, 1975)

[4]

J.N. Crossley, et.al., What is Mathematical Logic?, (Oxford University Press, 1978)

[5]

G. Chaitin, Gödel's Theorem and Information, International Journal of Theoretical Physics 22 (Plenum Publishing Corp., 1982) pp.941-954; reprinted in G.J. Chaitin, Information, Randomness, and Incompleteness (World Scientific,1987)

[6]

P.J. Cohen, Comments on the Foundations of Set Theory, in Proceedings of the Symposia in Pure Mathematics Volume XIII Part I, (American Mathematical Society, 1971)

[7]

N.J. Cutland, Computability, (Cambridge University Press, 1980)

[8]

D.C. Dennett, Brainstorms, (Harvester Wheatsheaf, 1981)

[9]

K. Fulves, Self-Working Number Magic (Dover, 1983)

[10]

J. Kalckar, Niels Bohr and his youngest disciples; in S. Rozental, ed., Niels Bohr: His life and work as seen by his friends and colleagues, (North-Holland, 1967)

[11]

R. Kirk, Mental Machinery and Gödel, Synthese 66 (D. Reidel Publishing Company, 1986) pp.437-452

[12]

M. Kline, Mathematics: The Loss of Certainty, (Oxford University Press, 1982)

[13]

J. Lucas, Minds, Machines and Gödel, Philosophy, Vol.XXXVI (Cambridge University Press, 1961); reprinted in Minds and Machines, ed. A.R. Anderson, (Prentice Hall, 1964)

[14]

R. Penrose, Shadows of the Mind, (Vintage, 1995)

[15]

R. Penrose, Psyche, Volume 2, Number 1 (1996) pp.89-129

[16]

H. Putnam, The Best of all Possible Brains (Review of Shadows of the Mind by R. Penrose), New York Times, 20 November 1994.

[17]

H. Putnam, Mathematics without foundations, Journal of Philosophy 64 (Journal of Philosophy Inc., 1967) pp.5-22; reprinted in Philosophy of Mathematics, edited by P. Benacerraf and H. Putnam, (Cambridge University Press, 1985)

[18]

D. Ruelle, Chance and Chaos, (Princeton University Press, 1991)

[19]

B. Russell, Portraits from Memory, Bertrand Russell Peace Foundation (George Allen and Unwin, 1956)

[20]

B. Russell, My Philosophical Development (Unwin, 1975).

[21]

A. Scott, Stairway to the Mind, (Copernicus, 1995)

[22]

J.R. Searle, Minds, Brains, and Programs, Behavioral and Brain Sciences 3 (Cambridge University Press, 1980) 417-24, reprinted in The Philosophy of Artificial Intelligence, ed. M.A. Boden, (Oxford University Press, 1990), pp.67-88

[23]

J.C. Shepherdson and H.E. Sturgis, `Computability of Recursive Functions', J. Assoc. Computing Machinery 10 (1963) 217-255

[24]

A. Turing, Computing Machinery and Intelligence, Mind 59 No.236 (Oxford University Press, 1950) 433-460, reprinted in The Philosophy of Artificial Intelligence, ed. M.A. Boden, (Oxford University Press, 1990), pp.40-66

[25]

A. Turing, Systems of Logic Based on Ordinals, P. Lond. Math. Soc. (2) 45 (1939) 161-228

[26]

J. von Neumann, The Mathematician. ``Works of the Mind.'' in Collected Works Volume 1, ed. A.H. Taub, (Pergamon Press, 1961)

[27]

J. von Neumann, The Computer and the Brain, (Yale University Press, 1958)

[28]

K. Warwick, March of the Machines, (Century, 1997)

Footnotes:

¹ For more details see Intel's website

http://www.intel.com/pressroom/archive/releases /cn121796.htm

http://www.sandia.gov/LabNews/LN06-20-97/teraflops_story.html

² In addition to Putnam's review, discussed here, an on-line version of Soloman Feferman's review of Shadows of the Mind can be found at

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

http://psyche.cs.monash.edu.au/v2/psyche-2-23-penrose.html

http://ling.ucsc.edu/ ~ chalmers/biblio4.html .2

http://ling.ucsc.edu/ ~ chalmers/biblio.html

³ Putnam's own view on the nature of human mentality is indicated by the following quote from [17]:

Why should all truths, even all empirical truths, be discoverable by probabilistic automata (which is what I suspect we are) using a finite amount of observational material?

⁴ All quotations from Turing's article in this chapter are reprinted by permission of Oxford University Press.

⁵ In 1990 Dr. Hugh Loebner pledged a Grand Prize of $100,000 for the first computer whose responses were indistinguishable from a human's. Each year a prize of $2000 is awarded to the most human computer, which this year was won on May 16, 1997 by the program Converse, entered by the University of Sheffield. The homepage of the Loebner prize is

http://acm.org/ ~ loebner/loebner-prize.htmlx

⁶ On May 11, 1997 the IBM computer Deep Blue won a six game match against the world chess champion Garry Kasparov. For more details see

http://www.chess.ibm.com/home/html/b.html

⁷ The difficulty in defining each and every concept one uses is nicely put [2] by Ludwig Boltzmann (1844-1906); reprinted by kind permission of Kluwer Academic Publishers:

Let me begin by defining my position by way of a true story. While I was still at high school my brother (long since dead) tried often and in vain to convince me how absurd was my ideal of a philosophy that clearly defined each concept at the time of introducing it. At last he succeeded as follows: during a lesson a certain philosophic work (I think by Hume) had been highly recommended to us for its outstanding consistency. At once I asked for it at the library, where my brother accompanied me. The book was available only in the original English. I was taken aback, since I knew not a word of English, but my brother objected at once: ``if the work fulfils your expectations, the language surely cannot matter, for then each word must in any case be clearly defined before it is used.''

⁸ To determine if the number of marbles in two bowls is the same, remove one marble from each bowl, then another marble from each bowl, and so on. If both bowls become empty at the same step then they contained the same number of marbles. If only one bowl is empty then they contained different numbers. (Then replace the marbles in their respective bowls.)

⁹ We do not allow instructions of the sort, for example, S(r₁), which adds a marble to the bowl with number equal to the content of register R₁. In fact, although we are using numbers as names for the bowls, any symbols could be used for these names. They do not have the same quantitative significance as the content of a bowl. We also do not allow instructions of the sort J(1,3,r₀) which may cause a jump to the instruction with number equal to the content of register R₀. Again, an instruction number and a number of marbles are two different types of things. One is an ordinal number, representing an ordering (first, second, etc.), the other a cardinal number, representing an amount.

¹⁰ The URM was invented by J.C.Shepherdson and H.E.Sturgis [23]. A nice discussion of the URM is given by N.J.Cutland [7].

¹¹ The working registers are R₀,R₁,R₂; the others remain unchanged and do not influence the computation.

¹² Used explicitly as part of the jump instructions and implicitly as part of the transfer instructions.

¹³ The case n = m is dealt with by the first application of J(1,2,7).

¹⁴ See Cutland [7] for further discussion of this and other assignments.

¹⁵ Here is a program to add l to any number (which is placed in register R₀, all other registers initialized to 0): S(0),S(0),¼,S(0) [l copies].

¹⁶ Here is a program to subtract 1 from any number m (which is placed in register R₀, all other registers initialized to 0): S(1),J(0,1,5),S(1),S(2),J(0,0,1),T(2,0),Z(1),Z(2). If m ³ 1, when you complete the execution of this program there will be m-1 in register R₀, all other registers containing 0. If m = 0, this program will not halt; i.e. you will never complete the program.

¹⁷ Even if you could carry out your reasoning without language, you could not communicate to others how you arrived at your conclusions unless a common language is agreed.

¹⁸ What rules of deduction should be included in the formal system? Is there only one correct logical system? Consider other areas of mathematics. What is the correct geometrical theory? The classical geometry of Euclid was considered the only correct geometry for thousands of years, but now we consider the correct geometry to be an empirical question. The curved space-time of Einstein's general relativity theory is considered a better mathematical model than the flat Euclidean geometry. What is the correct algebraic theory? The algebraic structure of a theory of observable quantities had been supposed to satisfy xy = yx (commutativity) and x(y+z) = xy+xz (distributivity). But now it is considered that quantum theory, involving non-commutative observables, is a better mathematical model of atomic phenomena. Quantum theory still keeps distributivity, but if the empirical data require it, then a further modification of the algebraic structure of the theory could be made. What is the correct logic? Perhaps there is no one correct logic. It may also depend on the properties of the system being modelled. We have empirical geometry, empirical algebra, why not empirical logic?

¹⁹ We could use a method similar to the one used to encode programs, since programs are finite sequences of instructions and formulas are finite sequences of symbols - and proofs are finite sequences of formulas. So first give numbers to each symbol in the alphabet of L. If f is the formula a₁¼a_b, where m_j is the Gödel number of the symbol a_j, then f is assigned the number h(m₀,¼,m_b), where the function h is given in (4). Similarly, if f₀,¼,f_b is a finite sequence of formulas where m_j is the Gödel number of the formula f_j, then the sequence of formulas is assigned the number h(m₀,¼,m_b).

²⁰ Different interpretations are often given to the same English sentence by different people. They may think they have a disagreement as to which statements are true, but actually they may simply have assigned a different meaning to the same words! This is called a problem of semantics.

²¹ Consequently, if the formal system is sound and if there is a formula f which is true in one interpretation and false in another, then neither f nor its negation can be a theorem of the formal system.

²² Someone else may interpret the formulas in a completely different way, as statements about some other activity or physical process.

²³ We suppose that when P_m halts, all its working registers other than R₀ contain 0. Similarly for P_M. This can always be arranged. In Figure we take the working registers of P_M to be R_k for k £ N_M.

²⁴ In our interpretation f_j expresses the statement S_j, that the j^th program does not produce the number j. However, in another interpretation f_j no longer has this meaning. The relation between f_j and S_j is lost.

²⁵ The element of self-reference in the definition is inevitable. The oracle must be able to refer to itself or to something dependent on the oracle. As we have seen in the case of formal systems, a formula can be written down which may be interpreted as stating that the self-same formula cannot be proved by the formal system.

²⁶ Recall the Feynman story above.

²⁷ On the other hand, if P_n does not produce n but a mathematician claims that it does (without any indication as to what input would produce n), it may not be possible to prove him wrong. There may be no way to determine the truth or falsity of S_n and the law of the excluded middle (every statement is either true or false) may not be applicable.

²⁸ Positive values of w_ji corresponds to exitation and negative values to inhibition. Given rational values for the weights, we can multiply through by a sufficiently large integer to rewrite the equations with integer-valued weights.

²⁹ Negative integers need not enter directly into the computation. Use may be made, for example, of the difference function Dif(n,m) = n-m if n ³ m and = 0 if n < m.

³⁰ We shall naturally suppose that a (finite) brain can have only finitely many beliefs at any one time.

³¹ What could be more computational than that?

³² It may be that the formal system F does not satisfy the requirements to deduce Gödel's theorem for F. But the point of the argument is that there are statements which H believes to be true but which are not theorems of the formal system F. This will undoubtedly be the case for mathematical statements of a sort which cannot even be expressed in the particular formal system F, and even more so for non-mathematical beliefs.

³³ If H's beliefs are not theorems of F, what are they? The beliefs are encoded into the Gödel belief number b(t), which is a term of the formal language.

³⁴ They only think they are.

³⁵ To the reader with such a brain: `Don't lose your marbles!'

³⁶ Well, maybe.

³⁷ According to the construction of present-day computers, we could also say that the demon corresponds to the CPU (central processing unit) of the computer, which, while executing a program, manipulates the numbers (on/off transistor patterns) stored in its registers and RAM memory locations.