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

A more general notion than loop is that of subroutine, or procedure, which we have already discussed somewhat. The basic idea here is that a group of operations are lumped together and considered a single unit with a name-such as the procedure
ORNATE NOUN
. As we saw in
RTN
's, procedures can call each other by name, and thereby express very concisely sequences of operations which are to be carried out. This is the essence of modularity in programming. Modularity exists, of course, in hi-fi systems, furniture, living cells, human society-wherever there is hierarchical organization.

More often than not, one wants a procedure which will act variably, according to context. Such a procedure can either be given a way of peering out at what is stored in memory and selecting its actions accordingly, or it can be explicitly fed a list of parameters which guide its choice of what actions to take. Sometimes both of these methods are used. In
RTN
terminology, choosing the sequence of actions to carry out amounts to choosing
which pathway to follow
. An
RTN
which has been souped up with parameters and conditions that control the choice of pathways inside it is called an
Augmented Transition Network
(
ATN
). A place where you might prefer
ATN
's to
RTN's
is in producing sensible-as distinguished from nonsensical-English sentences out of raw words, according to a grammar represented in a set of
ATN
's. The parameters and conditions would allow you to insert various semantic constraints, so that random juxtapositions like "a thankless brunch" would be prohibited. More on this in Chapter XVIII, however.

Recursion in Chess Programs

A classic example of a recursive procedure with parameters is one for choosing the "best"

move in chess. The best move would seem to be the one which leaves your opponent in the toughest situation. Therefore, a test for goodness of a move is simply this: pretend you've made the move, and now evaluate the board from the point of view of your opponent. But how does your opponent evaluate the position? Well, he looks for
his
best move. That is, he mentally runs through all possible moves and evaluates them from what he thinks is your point of view, hoping they will look bad to you. But

notice that we have now defined "best move" recursively, simply maxim that what is best for one side is worst for the other. The procedure which looks for the best move operates by trying a move and then
calling on itself in the role of opponent
! As such, it tries another n calls on itself in the role of its opponent's opponent-that is, its This recursion can go several levels deep-but it's got to bottom out somewhere!

How do you evaluate a board position
without
looking There are a number of useful criteria for this purpose, such as si number of pieces on each side, the number and type of pieces undo the control of the center, and so on. By using this kind of evaluation at the bottom, the recursive move-generator can pop back upwards an( evaluation at the top level of each different move. One of the parameters in the self-calling, then, must tell how many moves to look ahead. TI most call on the procedure will use some externally set value parameter. Thereafter, each time the procedure recursively calls must decrease this look-ahead parameter by 1. That way, w parameter reaches zero, the procedure will follow the alternate pathway -- the non-recursive evaluation.

In this kind of game-playing program, each move investigate the generation of a so-called "look-ahead tree", with the move trunk, responses as main branches, counter-responses as subsidiary branches, and so on. In Figure 38 I have shown a simple look-ahead tree depicting the start of a tic-tar-toe game. There is an art to figuring to avoid exploring every branch of a look-ahead tree out to its tip. trees, people-not computers-seem to excel at this art; it is known that top-level players look ahead relatively little, compared to most chess programs – yet the people are far better! In the early days of compute people used to estimate that it would be ten years until a computer (or
FIGURE 38. The branching tree of moves and countermoves at the start of c tic-tac-toe.

program) was world champion. But after ten years had passed, it seemed that the day a computer would become world champion was still more than ten years away ... This is just one more piece of evidence for the rather recursive

Hofstadter's Law
: It always takes longer than you expect, even when you take into account Hofstadter's Law.

Recursion and Unpredictability

Now what is the connection between the recursive processes of this Chapter, and the recursive sets of the preceding Chapter? The answer involves the notion of a
recursively
enumerable set
. For a set to be r.e. means that it can be generated from a set of starting points (axioms), by the repeated application of rules of inference. Thus, the set grows and grows, each new element being compounded somehow out of previous elements, in a sort of "mathematical snowball". But this is the essence of recursion-something being defined in terms of simpler versions of itself, instead of explicitly. The Fibonacci numbers and the Lucas numbers are perfect examples of r.e. sets-snowballing from two elements by a recursive rule into infinite sets. It is just a matter of convention to call an r.e. set whose complement is also r.e. "recursive".

Recursive enumeration is a process in which new things emerge from old things by fixed rules. There seem to be many surprises in such processes-for example the unpredictability of the Q-sequence. It might seem that recursively defined sequences of that type possess some sort of inherently increasing complexity of behavior, so that the further out you go, the less predictable they get. This kind of thought carried a little further suggests that suitably complicated recursive systems might be strong enough to break out of any predetermined patterns. And isn't this one of the defining properties of intelligence? Instead of just considering programs composed of procedures which can recursively
call
themselves, why not get really sophisticated, and invent programs which can
modify
themselves-programs which can act on programs, extending them, improving them, generalizing them, fixing them, and so on? This kind of "tangled recursion"

probably lies at the heart of intelligence.

Canon

by Intervallic Augmentation

Achilles and the Tortoise have just finished a delicious Chinese banquet for
two, at the best Chinese restaurant in town.

Achilles: You wield a mean chopstick, Mr. T.

Tortoise: I ought to. Ever since my youth, I have had a fondness for Oriental cuisine. And you-did you enjoy your meal, Achilles? Achilles: Immensely. I'd not eaten Chinese food before. This meal was a splendid introduction. And now, are you in a hurry to go, or shall we just sit here and talk a little while?

Tortoise: I'd love to talk while we drink our tea. Waiter!

(A waiter comes up.)

Could we have our bill, please, and some more tea?

(The waiter rushes off.)

Achilles: You may know more about Chinese cuisine than I do, Mr.T, I'll bet I know more about Japanese poetry than you do. Have you ever read any haiku?

Tortoise: I'm afraid not. What is a haiku?

Achilles: A haiku is a Japanese seventeen-syllable poem-or minipoem rather, which is evocative in the same way, perhaps, as a fragrant petal is, or a lily pond in a light drizzle. It generally consists of groups of: of five, then seven, then five syllables.

Tortoise: Such compressed poems with seventeen syllables can't much meaning ...

Achilles: Meaning lies as much in the mind of the reader as i haiku.

Tortoise: Hmm ... That's an evocative statement.

(The waiter arrives with their bill, another pot of tea, and two fortune cookies.)
Thank you, waiter. Care for more tea, Achilles?

Achilles: Please. Those little cookies look delicious. (
Picks one up, bites I into it and begins to
chew.
) Hey! What's this funny thing inside? A piece of paper?

Tortoise: That's your fortune, Achilles. Many Chinese restaurants give out fortune cookies with their bills, as a way of softening the blow. I frequent Chinese restaurants, you come to think of fortune cookies

less as cookies than as message bearers Unfortunately you seem to have swallowed some of your fortune. What does the rest say?

Achilles: It's a little strange, for all the letters are run together, with no spaces in between.

Perhaps it needs decoding in some way? Oh, now I see. If you put the spaces back in where they belong, it says, "ONE WAR TWO EAR EWE". I can't quite make head or tail of that. Maybe it was a haiku-like poem, of which I ate the majority of syllables.

Tortoise: In that case, your fortune is now a mere 5/17-haiku. And a curious image it evokes. If 5/17-haiku is a new art form, then I'd say woe, 0, woe are we ... May I look at it?

Achilles (
handing the Tortoise the small slip of paper
): Certainly.

Tortoise: Why, when I "decode" it, Achilles, it comes out completely different! It's not a 5/17-haiku at all. It is a six-syllable message which says, "0 NEW ART WOE ARE WE". That sounds like an insightful commentary on the new art form of 5/17-haiku.

Achilles: You're right. Isn't it astonishing that the poem contains its own commentary!

Tortoise: All I did was to shift the reading frame by one unit-that is, shift all the spaces one unit to the right.

Achilles: Let's see what your fortune says, Mr. Tortoise.

Tortoise (
deftly splitting open his cookie
,
reads
): "Fortune lies as much in the hand of the eater as in the cookie."

Achilles: Your fortune is also a haiku, Mr. Tortoise-at least it's got seventeen syllables in the 5-7-5 form.

Tortoise: Glory be! I would never have noticed that, Achilles. It's the kind of thing only you would have noticed. What struck me more is what it says-which, of course, is open to interpretation.

Achilles: I guess it just shows that each of us has his own characteristic way of interpreting messages which we run across ...

(Idly, Achilles gazes at the tea leaves on the bottom of his empty teacup.)
Tortoise: More tea, Achilles?

Achilles: Yes, thank you. By the way, how is your friend the Crab? I have been thinking about him a lot since you told me of your peculiar phonograph-battle.

Tortoise: I have told him about you, too, and he is quite eager to meet you. He is getting along just fine. In fact, he recently made a new acquisition in the record player line: a rare type of jukebox.

Achilles: Oh, would you tell me about it? I find jukeboxes, with their flashing colored lights and silly songs, so quaint and reminiscent of bygone eras.

Tortoise: This jukebox is too large to fit in his house, so he had a shed specially built in back for it.

Achilles: I can't imagine why it would be so large, unless it has an unusually large selection of records. Is that it?

Tortoise: As a matter of fact, it has exactly one record.

Achilles: What? A jukebox with only one record? That's a contradiction in terms. Why is the jukebox so big, then? Is its single record gigantic -- twenty feet in diameter?

Tortoise: No, it's just a regular jukebox-style record.

Achilles: Now, Mr. Tortoise, you must be joshing me. After all, what I of a jukebox is it that has only a single song?