The operation of addition for strings is called concatenation which means just writing the two summand strings one after another. For example "Bold" + "Eagle" = "BoldEagle". The operation is clearly associative but not commutative, for "Eagle" + "Bold" = EagleBold" and is not the same string as "BoldEagle". The empty string "" plays the role of zero. There is no inverse. Thus, given an alphabet, the set of all strings formed by letters from the alphabet is a semigroup.

In itself, concatenation of strings is an unremarkable operation. However, observe that it does encompass a very mundane activity of writing, perhaps also talking, and likely that of thinking. Except that in each we do not concatenate arbitrary strings and, more importantly, we do not concatenate them in an arbitrary order but following some grammar rules. So here we see a glimpse of a foundation for a recently developed science of mathematical linguistic.

As another application, by introducing a system of production rules we may attempt to formalize the processes of translation and programming. Production rules are the laws that govern how strings might be transformed into one another. An example taken from R.Smullyan, Satan, Cantor, and Infinity will help you better understand the meaning and significance of production rule systems.

## THE ISLAND OF ROBOTS

THE SORCERER and his friends Annabelle and Alexander retired early and rose in the wee hours of the morning and set sail for the Island of Robots. They arrived just about as the sun was rising and spent the time before lunch walking around observing the strange things that went on. This island was the noisiest place that Annabelle or Alexander had ever been to in their lives. The clinging and clanging and binging and banging and din and clatter were almost unbearable. And the things that went on! The whole island was bustling with metallic robots moving about, some apparently aimlessly, others creating new robots from various parts lying around, and others dismantling robots whose parts would often be used for creating other robots. Each robot bore a label consisting of a string of capital letters. Annabelle and Alexander at first thought the letters were merely for identification, but later found they were a program determining what the robot should do-whether it would walk around aimlessly or whether it would create other robots, and if so, what program the new robots would have, or whether it would be a destructive robot, and if so, what robots it would destroy.

One thing struck the couple as quite peculiar: They saw a robot pick up a bunch of pieces and construct a robot that looked identical to its creator; indeed it had the same program. Having the same program, this duplicate constructed a duplicate of itself, which in turn constructed a duplicate of itself, which in turn constructed a duplicate of itself (as a matter of fact, from parts of its great-grandparent, which had been dismantled by then). Indeed, this process could go on forever, unless something stopped it.

Next, the couple saw another curious thing: a robot - call it x - constructed a robot y, quite different from x, which then constructed a duplicate of x, which then constructed a duplicate of y, and this 2-cycle could go on forever!

Then they saw a 3-cycle: x constructed y, which constructed Z, which constructed (a duplicate of) x, which constructed (a duplicate of) y, . . .

Next they saw something very upsetting. A robot x constructed a robot y and the first thing y did when it was completed was to destroy its creator. This struck the couple as the height of ingratitude.

Then they saw a robot x destroy a robot y. Later on, y got reassembled and met x and immediately destroyed it. Then x got reassembled sometime later and destroyed y, and this could go on forever!

Next they saw two very different-looking robots, x and y, walk briskly toward each other and immediately begin dismantling each other, and soon all that was left was a rubble of parts.

Then they saw a robot x construct a robot y, which constructed a robot z, which then dismantled x. Thus x was destroyed by its own grandchild!

Next, they saw something quite sad: a suicidal robot dismantled itself, and all that was left was a pile of parts. (At a certain stage of dismantling, the robot pressed a button which caused what was left to fall completely apart.) Then another robot came by and reassembled the dismantled robot, but when the second robot left, the first one, still having the same program, destroyed itself again. There seemed to be no hope for this poor robot. If it were ever again reassembled, still with the same program, then it would have to destroy itself again; no robot with this program could possibly be stable.

"I'm completely bewildered by all this," said Annabelle. "I have no idea what in the world is going on!"

"Nor I," said Alexander.

"Oh, you will find out this afternoon," said the Sorcerer. "There are several robot stations on this island, each with its own programming system. After lunch, we will visit the laboratories of some of the engineers in charge. They will explain their systems to you."

## 1. THE SYSTEM OF CHARLES ROBERTS

After an excellent lunch, cooked and served by skilled robots, the Sorcerer took our two friends to the Northeast Station, whose director was a pleasant individual named Charles Roberts. After introducing his students to Roberts, the Sorcerer took his leave, explaining that he had some things to attend to on the island.

"Now for the details of my system," said Roberts with a smile. "As you have observed, each robot is labeled with a string of letters. These letters constitute a program determining just what the robot will do.

"Let me explain to you my terminology and notation," be continued. "By an expression or a combination, I mean any string of capital letters-for example, MLBP is an expression; so is LLAZLBA; so is a single letter like G standing alone. I use small letters like x, y, z, a, b, c to stand for particular strings of capital letters, and by xy I mean the combination x followed by the combination y. For example, if x is the expression M BP and y is the expression SLPG, then xy is the expression MBPSLPG. Also, Ax is then AMBP; xA is MBPA; GxH is GMBPH; CxLy is CMBPLSLPG. Do you get the idea?"

His visitors had no trouble grasping this.

"Now," explained Roberts, "my programming system is based on the idea of certain expressions being names of others. And I have two rules concerning the naming of expressions. My first rule is:

Rule Q. For any expression x, the expression Qx names x.

"Thus, for example, QBAF names BAF; QQH names QH; QDCD names DCD.

"We might refer to Qx as the principal name of x, but, as you will see, an expression x may have other names as well. My second naming rule is the following:

Rule R. If x names y, then Rx names yy.

"Thus, for example, RQB names BB, since QB names B. Or again, RQBR names BRBR, since QBR names BR. In general, for any expression x, the expression RQx names xx, since Qx names x. Do not make the common mistake of believing that Rx names xx; in general it does not. It is RQx that names xx.

"I call Rule R the repetition rule, because for any X, the expression xx is called the repeat of x-thus, ABCABC is the repeat of ABC. And so Rule R tells us that if x names y, then Rx names the repeat of y.

"To see if you have grasped these rules, what does RRQBH name?"

After a moment's thought, Alexander said: "It names BHBHBHBH."

"Because RQBH names BHBH, hence RRQBH must name the repeat of BHBH, which is BHBHBHBH."

"Good!" said Roberts.

"You said before," said Alexander, "that an expression can have more than one name. How can that happen?"

"Oh," said Roberts, "for example, xx has RQx as one name and Qxx as another. Both name xx. Or again, Qxxxx names xxxx, and so does RQxx, and so does RRQX. Thus Qxxxx, RQxx, RRQX are three different names for the same expression."

"Oh, of course!" said Alexander.

"How is all this related to some robots creating others?" asked Annabelle.

"Oh, my creation rule is a very simple one," said Roberts. "Remember that when we say that x creates y we mean that any robot with program x will create a robot with program y. Here is my creation rule.

Rule C. If x names y, then Cx creates y.

"Thus, for any y, robot CQy (that is, any robot with program CQy) creates robot y (a robot with program y).

"It also follows from our three rules that CRQX creates xx (since RQx names xx) and CRRQX creates xxxx (since RRQX names xxxx). And now, for some interesting applications."

### * 1 *

"You have seen self-producing robots on this island, robots that create duplicates of themselves?"

"Oh, yes," said Annabelle.

"Well, can you now give me a program for one. That is, can you find an x such that x creates x?"

### * 2 *

"Very good," said Roberts, after the couple showed him their solution.

"And now," he continued, "before we turn to any more problems about creation, there are some basic principles about naming that you should grasp. For one thing, can you find some x that names itself?"

### * 3 *

"Excellent," said Roberts. "Can you find another x that names itself, or is there only one?"

### * 4 *

"You said before," said Alexander, "that in general, Rx does not name xx. Can it ever happen, by some sort of coincidence maybe, that Rx does name xx? That is, is there any x such that Rx names xx?"

"What a curious question," said Roberts. "I never thought about that before. Let's see now."

At this point, Roberts took out pencil and paper and made some calculations. "Yes," he said after a while, "there does happen to be such an expression x. Can you find it?"

### * 5 * Some More Curiosities

"If you like curiosities," said Roberts, "it might amuse you to know that for each of the following conditions there is some x that satisfies that condition.

```(a)	Rx names x.
(b)	RQx names QRx.
(c)	Rx names Qx.
(d)	RRx names QQx.
(e)	RQx names RRx.
```

"But these are only curiosities," added Roberts, "and have no applications that I know of to robot programming. You might have fun working them out sometime at your leisure, if you like puzzles for their own sake, regardless of practical applications."

Some Fixed-Point Principles "We saw some robots destroying others," said Alexander. "Does your program provide for these?"

"No," replied Roberts, "the destruction programs are in the hands of my brother, Daniel Chauncey Roberts, who is also a roboteer on this island. His programs are very interesting, and you should make a point of visiting him today.

"And now, I will tell you of a basic principle underlying many of my programs as well as those of my brother."

## References

1. R. Smullyan, Satan, Cantor, and Infinity and other mind boggling puzzles, Oxford University Press (February 18, 1993)
[an error occurred while processing this directive]