Gödel, Escher, Bach: An Eternal Golden Braid (100 page)

Crab: Well, uh ... (Shifts in his chair, and looks somewhat uncomfortable.) Achilles: What's the matter? Is it harder to decide whether this piece is beautiful than it is for other pieces?

Crab: Ahm ... No, it's not that-not at all. It's just that, well ... I really have to HEAR a piece before I can tell how much I like it.

Achilles: So go ahead and play it! I'm dying to know whether you find it beautiful or not.

Crab: Of course, I'd be extremely glad to play it for you. The only thing is Achilles: Can't you play it for me? What's the matter? Why are you balking?

Tortoise: Don't you realize, Achilles, that for Mr. Crab to fulfill your request would be most impolite and disturbing to the clientele and employees of this fine establishment?

Crab (suddenly looking relieved): That's right. We have no right to impose our music on others.

Achilles (dejectedly): Oh, PHOOEY! And I so much wanted to know what he thinks of this piece!

Crab: Whew! That was a close call!

Achilles: What was that remark?

Crab: Oh-nothing. It's just that that waiter over there, he got knocked into by another waiter, and almost dropped a whole pot of tea into a lady's lap. A narrow escape, I must say.

What do you say, Mr. Tortoise? Tortoise: Very good teas, I'd say. Wouldn't you agree, Achilles? Achilles: Oh, yes. Prime teas, in fact.

Crab: Definitely. Well, I don't know about you two, but I should perhaps be going, for I've a long steep trail back to my house, on the other side of this hill.

Achilles: You mean this is a big bluff?

Crab: You said it, Achilles.

Achilles: I see. Well, I'll have to remember that.

Crab: It has been such a jolly afternoon, Achilles, and I sincerely hope we will exchange more musical compositions another day.

Achilles: I'm looking forward to that very much, Mr. C. Well, good-bye. Tortoise: Good-bye, Mr. C.

(And the Crab heads off down his side of the hill.)

Achilles: Now there goes a brilliant fellow ... In my estimation, he's at least four times as smart as any crab alive. Or he might even be five

Tortoise: As you said in the beginning, and probably shall be saying forevermore, words without end.

Church, Turing, Tarski, and Others

Formal and Informal Systems

WE HAVE COME to the point where we can develop one of the main theses of this book: that every aspect of thinking can be viewed as a high-level description of a system which, on a low level, is governed by simple, even formal, rules. The "system", of course, is a brain-unless one is' speaking of thought processes flowing in another medium, such as a computer's circuits. The image is that of a formal system underlying an "informal system"-a system which can, for instance, make puns, discover number patterns, forget names, make awful blunders in chess, and so forth. This is what one sees from the outside: its informal, overt, software level. By contrast, it has a formal, hidden, hardware level (or "substrate") which is a formidably complex mechanism that makes transitions from state to state according to definite rules physically embodied in it, and according to the input of signals which impinge on it.

A vision of the brain such as this has many philosophical and other consequences, needless to say. I shall try to spell some of them out in this Chapter. Among other things, this vision seems to imply that, at bottom, the brain is some sort of a "mathematical"

object. Actually, that is at best a very awkward way to look at the brain. The reason is that, even if a brain is, in a technical and abstract sense, some sort of formal system, it remains true that mathematicians only work with simple and elegant systems, systems in which everything is extremely clearly defined-and the brain is a far cry from that, with its ten billion or more semi-independent neurons, quasi-randomly connected up to each other. So mathematicians would never study a real brain's networks. And if you define

"mathematics" as what mathematicians enjoy doing, then the properties of brains are not mathematical.

The only way to understand such a complex system as a brain is by chunking it on higher and higher levels, and thereby losing some precision at each step. What emerges at the top level is the "informal system" which obeys so many rules of such complexity that we do not yet have the vocabulary to think about it. And that is what Artificial Intelligence research is hoping to find. It has quite a different 'flavor from mathematics research. Nevertheless, there is a loose connection to mathematics: Al people often come from a strong mathematics background, and

mathematicians sometimes are intrigued by the workings of their own brains. The following passage, quoted from Stanislaw Ulam's autobiographical
Adventures of a
Mathematician
, illustrates this point:

It seems to me that more could be done to elicit ... the nature of associations, with computers providing the means for experimentation. Such a study would have to involve a gradation of notions, of symbols, of classes of symbols, of classes of classes, and so on, in the same way that the complexity of mathematical or physical structures is investigated.

There must be a trick to the train of thought, a recursive formula. A group of neurons starts working automatically, sometimes without external impulse. It is a kind of iterative process with a growing pattern. It wanders about in the brain, and the way it happens must depend on the memory of similar patterns.'

Intuition and the Magnificent Crab

Artificial Intelligence is often referred to as "Al". Often, when I try to explain what is meant by the term, I say that the letters "AI" could just as well stand for "Artificial Intuition", or even "Artificial Imagery". The aim of Al is to get at what is happening when one's mind silently and invisibly chooses, from a myriad alternatives, which one makes most sense in a very complex situation. In many real-life situations, deductive reasoning is inappropriate, not because it would give wrong answers, but because there are too many correct but irrelevant statements which can be made; there are just too many things to take into account simultaneously for reasoning alone to be sufficient. Consider this mini-dialogue:

"The other day I read in the paper that the--

"Oh-you were reading? It follows that you have eyes. Or at least
one
eye. Or rather, that you had at least one eye
then
."

A sense of judgment-"What is important here, and what is not?"-is called for. Tied up with this is a sense of simplicity, a sense of beauty. Where do these intuitions come from?

How can they emerge from an underlying formal system?

In the
Magnificrab
, some unusual powers of the Crab's mind are revealed. His own version of his powers is merely that he listens to music and distinguishes the
beautiful
from the
non-beautiful
. (Apparently for him there is a sharp dividing line.) Now Achilles finds another way to describe the Crab's abilities: the Crab divides statements of number theory into the categories true and false. But the Crab maintains that, if he chances to do so, it is only by the purest accident, for he is, by his own admission, incompetent in mathematics. What makes the Crab's performance all the more mystifying to Achilles, however, is that it seems to be in direct violation of a celebrated result of metamathematics with which Achilles is familiar:

CHURCH's THEOREM: There is no infallible method for telling theorems of TNT from nontheorems.

It was proven in 1936 by the American logician Alonzo Church. Closely related is what I call the

TARSKI-CHURCH-TURING THEOREM: There is no infallible method for telling true from false statements of number theory.

The Church-Turing Thesis

To understand Church's Theorem and the Tarski-Church-Turing Theorem better, we should first describe one of the ideas on which they are based; and that is the Church-Turing Thesis (often called "Church's Thesis"). For the Church-Turing Thesis is certainly one of the most important concepts in the philosophy of mathematics, brains, and thinking.

Actually, like tea, the Church-Turing Thesis can be given in a variety of different strengths. So I will present it in various versions, and we will consider what they imply.

The first version sounds very innocent-in fact almost pointless:

CHURCH-TURING THESIS, TAUTOLOGICAL VERSION: Mathematics

problems can be solved only by doing mathematics.

Of course, its meaning resides in the meaning of its constituent terms. By "mathematics problem" I mean the problem of deciding whether some number possesses or does not possess a given arithmetical property. It turns out that by means of Godel-numbering and related coding tricks, almost any problem in any branch of mathematics can be put into this form, so that "mathematics problem" retains its ordinary meaning. What about "doing mathematics"? When one tries to ascertain whether a number has a property, there seem to be only a small number of operations which one uses in combination over and over again-addition, multiplication, checking for equality or inequality. That is, loops composed of such operations seem to be the only tool we have that allows us to probe the world of numbers. Note the word "seem". This is the critical word which the Church-Turing Thesis is about. We can give a revision:

CHURCH-TURING THESIS, STANDARD VERSION: Suppose there is a method which a sentient being follows in order to sort numbers into two classes.

Suppose further that this method always yields an answer within a finite amount of time, and that it always gives the same answer for a given number. Then: Some terminating FlooP program (i.e., some general recursive function) exists which gives exactly the same answers as the sentient being's method does.

The central hypothesis, to make it very clear, is that any mental process which divides numbers into two sorts can be described in the form of a FlooP program. The intuitive belief is that there are no other tools than those in FlooP, and that there are no ways to use those tools other than by

unlimited iterations (which FlooP allows). The Church-Turing Thesis is not a provable fact in the sense of a Theorem of mathematics-it is a hypothesis about the processes which human brains use.

The Public-Processes Version

Now some people might feel that this version asserts too much. These people might put their objections as follows: "Someone such as the Crab might exist-someone with an almost mystical insight into mathematics, but who is just as much in the dark about his own peculiar abilities as anyone else-and perhaps that person's mental mechanisms carry out operations which have no counterpart in FlooP." The idea is that perhaps we have a subconscious potential for doing things which transcend the conscious processes-things which are somehow inexpressible in terms of the elementary FlooP operations. For these objectors, we shall give a weaker version of the Thesis, one which distinguishes between public and private mental processes:

CHURCH-TURING THESIS, PUBLIC-PROCESSES VERSION: Suppose there is a method which a sentient being follows in order to sort numbers into two classes. Suppose further that this method always yields an answer within a finite amount of time, and that it always gives the same answer for a given number.

Proviso. Suppose also that this method can be communicated reliably from one sentient being to another by means of language. Then: Some terminating FlooP

program (i.e., general recursive function) exists which gives exactly the same answers as the sentient beings' method does.

This says that public methods are subject to "FlooPification", but asserts nothing about private methods. It does not say that they are un-FlooP-able, but it at least leaves the door open.

Srinivasa Ramanujan

As evidence against any stronger version of the Church-Turing Thesis, let us consider the case of the famous Indian mathematician of the first quarter of the twentieth century, Srinivasa Ramanujan (1887-1920). Ramanujan (Fig. 105) came from Tamilnadu, the southernmost part of India, and studied mathematics a little in high school. One day, someone who recognized Ramanujan's talent for math presented him with a copy of a slightly out-of-date textbook on analysis, which Ramanujan devoured (figuratively speaking). He then began making his own forays into the world of analysis, and by the time he was twenty-three, he had made a number of discoveries which he considered worthwhile. He did not know to whom to turn, but somehow was told about a professor of mathematics in faraway England, named G. H. Hardy. Ramanujan compiled his best