Read Gödel, Escher, Bach: An Eternal Golden Braid Online

Authors: Douglas R. Hofstadter

Tags: #Computers, #Art, #Classical, #Symmetry, #Bach; Johann Sebastian, #Individual Artists, #Science, #Science & Technology, #Philosophy, #General, #Metamathematics, #Intelligence (AI) & Semantics, #G'odel; Kurt, #Music, #Logic, #Biography & Autobiography, #Mathematics, #Genres & Styles, #Artificial Intelligence, #Escher; M. C

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

BOOK: Gödel, Escher, Bach: An Eternal Golden Braid
12.21Mb size Format: txt, pdf, ePub
ads

Figure 10. Mobius strip by M.C.Escher (wood-engraving printed from four blocks, 1961) ACHILLES:

Oh, yes, it comes back to me now: the famous Zen koan about Zen Master Zeno. As you say it is very simple indeed.

TORTOISE:

Zen Koan? Zen Master? What do you mean?

ACHILLES:

It goes like this: Two monks were arguing about a flag. One said, “The flag is moving.” The other said, “The wind is moving.” The sixth patriarch, Zeno, happened to be passing by. He told them, “Not the wind, not the flag, mind is moving.”

TORTOISE:

I am afraid you are a little befuddled, Achilles. Zeno is no Zen master, far from it. He is in fact, a Greek philosopher from the town of Elea (which lies halfway between points A and B). Centuries hence, he will be celebrated for his paradoxes of motion. In one of those paradoxes, this very footrace between you and me will play a central role.

ACHILLES:

I’m all confused. I remember vividly how I used to repeat over and over the names of the six patriarchs of Zen, and I always said, “The sixth patriarch is Zeno, The sixth patriarch is Zeno…” (
Suddenly a soft warm breeze picks up.
) Oh, look Mr.

Tortoise – look at the flag waving! How I love to watch the ripples shimmer through it’s soft fabric. And the ring cut out of it is waving, too!

TORTOISE: Don´t be silly. The flag is impossible, hence it can’t be waving. The wind is waving.

(At this moment, Zeno happens by.)

Zeno: Hallo! Hulloo! What’s up? What’s new?

ACHILLES: The flag is moving.

TORTOISE: The wind is moving.

Zeno: O friends, Friends! Cease your argumentation! Arrest your vitriolics! Abandon your discord! For I shall resolve the issue for you forthwith. Ho! And on such a fine day.

ACHILLES: This fellow must be playing the fool.

TORTOISE: No, wait, Achilles. Let us hear what he has to say. Oh Unknown Sir, do impart to us your thoughts on this matter.

Zeno: Most willingly. Not thw ind, not the flag – neither one is moving, nor is anything moving at all. For I have discovered a great Theorem, which states; “Motion Is Inherently Impossible.” And from this Theorem follows an even greater Theorem – Zeno’s Theorem: “Motion Unexists.”

ACHILLES: “Zeno’s Theorem”? Are you, sir, by any chance, the philosopher Zeno of Elea?

Zeno: I am indeed, Achilles.

ACHILLES:
(scratching his head in puzzlement
). Now how did he know my name?

Zeno: Could I possibly persuade you two to hear me out as to why this is the case? I’ve come all the way to Elea from point A this afternoon, just trying to find someone who’ll pay some attention to my closely honed argument. But they’re all hurrying hither and thither, and they don’t have time. You’ve no idea how disheartening it is to meet with refusal after refusal. Oh, I’m sorry to burden you with my troubles, I’d just like to ask you one thing: Would the two of you humour a sill old philosopher for a few moments – only a few, I promise you – in his eccentric theories.

ACHILLES: Oh, by all means! Please do illuminate us! I know I speak for both of us, since my companion, Mr. Tortoise, was only moments ago speaking of you with great veneration –

and he mentioned especially your paradoxes.

Zeno: Thank you. You see, my Master, the fifth patriarch, taught me that reality is one, immutable, and unchanging, all plurality, change, and motion are mere illusions of the sense. Some have mocked his views; but I will show the absurdity of their mockery. My argument is quite simple. I will illustrate it with two characters of my own Invention: Achilles )a Greek warrior, the fleetest of foot of all mortals), and a Tortoise. In my tale, they are persuaded by a passerby to run a footrace down a runway towards a distant flag waving in the breeze. Let us assume that, since the Tortoise is a much slowerrunner, he gets a head start of, say, ten rods. Now the race begins. In a few bounds Achilles has reached the spot where the Tortoise started.

ACHILLES: Hah!

Zeno: And now the Tortoise is but a single rod ahead of Achilles. Within only a moment, Achilles has attained that spot.

ACHILLES: Ho ho!

Zeno: Yet, in that short moment, the Tortoise has managed to advance a slight amount. In a flash, Achilles covers that distance too.

ACHILLES: Hee hee hee!

Zeno: But in that very short flash, the Tortoise has managed to inch ahead by ever so little, and so Achilles is still behind. Now you see that in order for Achilles to catch the Tortoise, this game of “try-to-catch-me” will have to be played an INFINITE number of times –

and therefore Achilles can NEVER catch up with the Tortoise.

TORTOISE: Heh heh heh heh!

ACHILLES: Hmm… Hmm… Hmm… Hmm… Hmm…That argument sounds wrong to me.

And yes, I can’t quite make out what’s wrong with it

Zeno: Isn’t it a teaser? It’s my favourite paradox.

TORTOISE: Excuse me, Zeno, but I believe your tale illustrates the wrong principle, doe sit not? You have just told us what will come to known, centuries hence, as Zeno’s “Achilles paradox” , which shows (ahem!) that Achilles will never catch the Tortoise; but the proof that Motion Is Inherently Impossible (and thence that Motion Unexists) is your

“dichotomy paradox”, isn’t that so?

Zeno: Oh, shame on me. Of course, you’re right. That’s the new one about how, in going from A to B, one has to go halfway first – and of that stretch one also has to go halfway, and so on and so forth. But you see, both those paradoxes really have the same flavour. Frankly, I’ve only had one Great Idea – I just exploit it in different ways.

ACHILLES: I swear, these arguments contain a flaw. I don’t quite see where, but they cannot be correct.

Zeno: You doubt the validity of my paradox? Why not just try it out|? You see that red flag waving down here, at the far end of the runway?

ACHILLES: The impossible one, based on an Escher print?

Zeno: Exactly. What do you say to you and Mr. Tortoise racing for it, allowing Mr. T a fair head start of, well, I don’t know –

TORTOISE: How about ten rods?

Zeno: Very good – ten rods.

ACHILLES: Any time.

Zeno: Excellent! How exciting! An empirical test of my rigorously proven Theorem! Mr.

Tortoise, will you position yourself ten rods upwind?

(The Tortoise moves ten rods closer to the flag)

Tortoise and Achlles: Ready!

Zeno: On your mark! Get set! Go!

Chapter 1
The MU-puzzle

Formal Systems

ONE OF THE most central notions in this book is that of a
formal system
. The type of formal system I use was invented by the American logician Emil Post in the 1920's, and is often called a "Post production system". This Chapter introduces you to a formal system and moreover, it is my hope that you will want to explore this formal system at least a little; so to provoke your curiosity, I have posed a little puzzle.

"Can you produce
MU
?" is the puzzle. To begin with, you will be supplied with a
string
(which means a string of letters).* Not to keep you in suspense, that string will be
MI
. Then you will be told some rules, with which you can change one string into another.

If one of those rules is applicable at some point, and you want to use it, you may, but-there is nothing that will dictate which rule you should use, in case there are several applicable rules. That is left up to you-and of course, that is where playing the game of any formal system can become something of an art. The major point, which almost doesn't need stating, is that you must not do anything which is outside the rules. We might call this restriction the "Requirement of Formality". In the present Chapter, it probably won't need to be stressed at all. Strange though it may sound, though, I predict that when you play around with some of the formal systems of Chapters to come, you will find yourself violating the Requirement of Formality over and over again, unless you have worked with formal systems before.

The first thing to say about our formal system-the
MIU
-
system
-is that it utilizes only three letters of the alphabet:
M, I, U
. That means that the only strings of the
MIU
-

system are strings which are composed of those three letters. Below are some strings of the
MIU
-system:

MU

UIM

MUUMUU

UIIUMIUUIMUIIUMIUUIMUIIU

* In this book, we shall employ the following conventions when we refer to strings. When the string is in the same typeface as the text, then it will be enclosed in single or double quotes.

Punctuation which belongs to the sentence and not to the string under discussion will go
outside
of the quotes, as logic dictates. For example, the first letter of this sentence is 'F', while the first letter of 'this ‘sentence’.is 't'. When the string is in
Quadrata Roman
, however, quotes will usually be left off, unless clarity demands them. For example, the first letter of
Quadrata
is
Q.

But although all of these are legitimate strings, they are not strings which are "in your possession". In fact, the only string in your possession so far is
MI
. Only by using the rules, about to be introduced, can you enlarge your private collection. Here is the first rule:

RULE I: If you possess a string whose last letter is
I,
you can add on a
U
at the end.

By the way, if up to this point you had not guessed it, a fact about the meaning of "string"

is that the letters are in a fixed order. For example,
MI
and
IM
are two different strings.

A string of symbols is not just a "bag" of symbols, in which the order doesn't make any difference.

Here is the second rule:

RULE II: Suppose you have
Mx
. Then you may add
Mxx
to your collection.

What I mean by this is shown below, in a few examples.

From
MIU
, you may get
MIUIU
.

From
MUM
, you may get
MUMUM
.

From
MU
, you may get
MUU
.

So the letter `x' in the rule simply stands for any string; but once you have decided which string it stands for, you have to stick with your choice (until you use the rule again, at which point you may make a new choice). Notice the third example above. It shows how, once you possess
MU
, you can add another string to your collection; but you have to get
MU
first! I want to add one last comment about the letter `x': it is not part of the formal system in the same way as the three letters `
M'
, `
I'
, and `
U'
are. It is useful for us, though, to have some way to talk in general about strings of the system, symbolically-and that is the function of thèx': to stand for an arbitrary string. If you ever add a string containing an 'x' to your "collection", you have done something wrong, because strings of the
MIU
-system never contain "x" “s”!

Here is the third rule:

RULE III: If
III
occurs in one of the strings in your collection, you may make a new string with
U
in place of
III
.

Examples:

From
UMIIIMU
, you could make
UMUMU
.

From
MII11
, you could make
MIU
(also
MUI
).

From
IIMII
, you can't get anywhere using this rule.

(The three I's have to be consecutive.)

From
MIII
, make
MU
.

Don't, under any circumstances, think you can run this rule backwards, as in the following example:

From
MU
, make
MIII
<- This is wrong.

Rules are one-way.

Here is the final rule.

RULE IV: If
UU
occurs inside one of your strings, you can drop it.

From
UUU
, get
U
.

From
MUUUIII
, get
MUIII
.

There you have it. Now you may begin trying to make
MU
. Don't worry you don't get it.

Just try it out a bit-the main thing is for you to get the flavor of this
MU
-puzzle. Have fun.

Theorems, Axioms, Rules

The answer to the MU-puzzle appears later in the book. For now, what important is not finding the answer, but looking for it. You probably hay made some attempts to produce MU. In so doing, you have built up your own private collection of strings. Such strings, producible by the rules, are called
theorems
. The term "theorem" has, of course, a common usage mathematics which is quite different from this one. It means some statement in ordinary language which has been proven to be true by a rigorous argument, such as Zeno's Theorem about the "unexistence" of motion, c Euclid's Theorem about the infinitude of primes. But in formal system theorems need not be thought of as statements-they are merely strings c symbols. And instead of being
proven
, theorems are merely
produced
, as if F machine, according to certain typographical rules. To emphasize this important distinction in meanings for the word "theorem", I will adopt the following convention in this book: when "theorem" is capitalized, its meaning will be the everyday one-a Theorem is a statement in ordinary language which somebody once proved to be true by some sort of logic argument. When uncapitalized, "theorem" will have its technical meaning a string producible in some formal system. In these terms, the MU-puzzle asks whether
MU
is a theorem of the
MIU
-system.

BOOK: Gödel, Escher, Bach: An Eternal Golden Braid
12.21Mb size Format: txt, pdf, ePub
ads

Other books

B00AO57VOY EBOK by Myers, AJ
Wrecked by Harmon, AJ
Return to Sender by Fern Michaels
The Town in Bloom by Dodie Smith
The Maiden and Her Knight by Margaret Moore
In a Heartbeat by Rita Herron
The Iscariot Sanction by Mark Latham
Sword of Apollo by Noble Smith