To Mock a Mocking Bird
Page 16
2 · We originally took Q1 to be BCB. But in terms of J and I, we can take Q1 to be JI, because JIxyz = Ix(Izy) = x(Izy) = x(zy).
3 · We can take T to be Q1I, because Q1Ixy = I(yx) = yx.
In terms of J and I, we can take T to be JII.
4 · JTxyz = Tx(Tzy) = Tx(yz) = yzx. Therefore JT is a robin.
In terms of J and I, we can therefore take R to be J(JII).
5 · We can take C* to be Q1C, because C(Q1C)xyzw = Q1Cyxzw = C(xy)zw = xywz.
Then we can take B to be C*Q1, because C*Q1xyz = Q1xzy = x(yz). Therefore C*Q1 is a bluebird.
In terms of C and Q1, B = (Q1C)Q1.
6 · BJTxyzw = J(Tx)yzw = Txy(Txwz) = yx(wxz). And so we take J1 to be BJT.
7 · First let’s follow Griffin’s hint. Well, J1xTTT = Tx(TxT) = Tx(Tx) = (Tx)x = Txx = xx.
Now, J1xTTT = CJ1TxTT = C(CJ1T)TxT = C(C(CJ1T)T)Tx. And so we take M to be C(C(CJ1T)T)T. In terms of B, C, T, and J, M = C(C(C(BJT)T)T)T. A bizarre expression for a mockingbird indeed! But it works.
As Curry remarked, the combinator J seems extremely artificial. It certainly does, but it yields the theoretically interesting result that the class of all combinators derivable from B, T, M, and I contains two combinators from which all the others are derivable.
APPENDIX
For the reader who is interested, here is a recipe for deriving any aristocratic bird from the four birds B, C, S, and I.
We use the notion of α-eliminates as defined in the last chapter. Let us call an expression X a nice expression if it is built up from the letters B, C, S, T, and variables. The letter K is definitely not allowed! What now needs to be shown is that if X is any nice expression, and if α is any variable which actually occurs in X, then we can find a nice α-eliminate of X. The procedure we describe for finding it will in fact lead to a unique nice α-eliminate of X, which we will call the distinguished α-eliminate of X. Our procedure is again a recursive one in the sense that the problem of finding the distinguished α-eliminate of a compound expression XY is sometimes reduced to the problem of first finding the distinguished α-eliminate of X and the distinguished α-eliminate of Y.
Here are the rules of the procedure.
Rule 1: The distinguished α-eliminate of α itself is I.
Rule 2: If α does not occur in X, then the distinguished α-eliminate of Xα is simply X.
Rule 3: Now consider a compound expression XY in which α occurs. Then α must occur in either X or Y and possibly in both. We assume that Y does not consist of just the variable α, because otherwise the situation reduces to Rule 2. Let X1 be the distinguished α-eliminate of X and let Y1 be the distinguished α-eliminate of Y. Assuming you have already found X1 and Y1, here is how to find the distinguished α-eliminate of XY.
a. If α occurs in both X and Y, then take SX1Y1 as the distinguished α-eliminate of XY.
b. If α occurs in Y but not in X, then take BXY1 as the distinguished α-eliminate of XY.
c. If α occurs in X but not in Y, take CX1Y as the distinguished α-eliminate of XY.
Let’s consider some examples:
1. What is the distinguished z-eliminate of yz? By Rule 2 it is y.
2. What is the distinguished z-eliminate of zy? The applicable rule here is part c of Rule 3: We must first obtain the distinguished z-eliminate of z; this is I, by Rule 1. Then by part c of Rule 3, the distinguished z-eliminate of zy is CIy. We can check; CIyz = Izy = zy.
3. Find the distinguished y-eliminate of y(xy). Solution: I is the distinguished y-eliminate of y and x is the distinguished y-eliminate of xy, so SIx is the distinguished y-eliminate of y(xy)—according to part a of Rule 3.
4. Find the distinguished y-eliminate of z(xy). Solution: x is the distinguished y-eliminate of xy, so Bzx is the distinguished y-eliminate of z(xy). Checking this is obvious: Bzxy = z(xy).
Exercise: In terms of B, C, S, and I, find a combinator A satisfying the condition Axyz = xz(zy). The problem should be divided into three parts:
a. Find the distinguished z-eliminate of xz(zy).
b. Find the distinguished y-eliminate of the expression obtained in (a).
c. Find the distinguished x-eliminate of the expression found in (b). This is the desired expression A. Verify that it really works!
20
Craig’s Discovery
“I have a question for you,” said Craig to Griffin the next day. “Consider the class of all birds derivable from just the three birds B, T, and I. Now—”
“Oh, that’s an interesting class!” interrupted Griffin. “This class has been studied by J. B. Rosser in connection with certain logics in which duplicative birds like M, W, L, S, and J have no place. Rosser was therefore interested in the class of birds derivable from B, C, and I, but this is the same class as you have just described. Now, what do you want to know about it?”
“Can you replace the three birds B, T, and I by just two members of this class from which all members of the class are derivable?”
“That’s an interesting question!” said Griffin. “I’ve never thought about it.”
“Well,” said Craig, “I was thinking about it last night, and I believe I’ve found the answer. I have discovered a bird derivable from just B and T such that both B and T are derivable from this bird together with I.”
“How interesting!” cried Griffin. “What bird is that?”
“It is the goldfinch G,” replied Craig. “The bird defined by the condition Gxyzw = xw(yz). Well, I have been able to derive B and T from G and I, hence the class of birds derivable from B, T, and I is the same as the class of birds derivable from G and I.”
“That’s neat!” said Griffin. “How do you get B and T from G and I?”
“Getting T is simple,” replied Craig, “but I had a lot of trouble getting B. Here, let me show you what I have done.
• 1 •
“The first thing I did was to derive the quirky bird—the bird Q3 satisfying the condition Q3xyz = z(xy). This bird is easily derivable from G and I. Do you see how?”
• 2 •
“Although this is a side issue, I might mention that the thrush T is easily derivable from Q3 and I—hence from G and I. Can you see how?”
• 3 •
“The important thing is to get the cardinal C,” said Craig. “Can you see how to get C from G and I?”
• 4 •
“Now that we have C,” said Craig, “we have CC, which is a robin R. Then from R, G, and Q3 we can get the queer bird Q. Do you see how? Then, of course, once we have Q and C, we have CQ, which is a bluebird B.”
“Excellent!” said Griffin, after he solved these problems. “I’m delighted that after such a short time, you have begun to do original work in this field!”
SOLUTIONS
1 · GI is a quirky bird, since GIxyz = Iz(xy) = z(xy). So we take Q3 to be GI.
2 · Q3I is a thrush, since Q3Ixy = y(Ix) = yx.
3 · GGII is a cardinal, since GGIIxyz = Gx(II)yz = GxIyz = xz(Iy) = xzy.
4 · GRQ3 is a queer bird, since GRQ3xyz = Ry(Q3x)z = Q3xzy = y(xz). So we take Q to be GRQ3.
We might note that GR is in fact a cardinal once removed, as the reader can easily verify, and so we could take C* to be GR. Then C*Q3 is a queer bird Q.
PART SIX
THE GRAND
QUESTION!
21
The Fixed Point Principle
Two days later, Craig had another session with Professor Griffin.
“Today,” said Griffin, “I wish to show you an important principle known as the fixed point principle, which will have many applications to various topics that I plan to discuss with you later on. A special case of this principle you already know—namely, that every bird here is fond of at least one bird. Before telling you the general principle, I think it would be helpful to consider a couple of special cases. If you can solve these special cases, I’m sure you will have no trouble grasping the fixed point principle.”
• 1 •
“How do you
find a bird A such that for any bird y, Ay = yA(AyA)?”
• 2 •
“How do you find a bird A such that for any birds y and z, Ayz = (z(yA))(yAz)?”
SOLUTIONS
Inspector Craig happened to be exceptionally alert that day, and he solved the two problems in a surprisingly short time.
“I can see two different ways of going about this,” said Craig. “One method uses the fact that every bird is fond of at least one bird; the other method proceeds, as it were, from scratch.
“Using the first method, here is how I solve your Problem 1. Consider the expression yx(xyx)—it is like yA(AyA) except that it has the letter x in place of the letter A. Now, by taking an x-y-eliminate of yx(xyx), we can find a bird A1 such that for any birds x and y, A1xy = yx(xyx).”
“Right, so far,” said Griffin.
“Well, this bird A1 is fond of some bird A—specifically, the bird LA1(LA1), with L as a lark. Thus A1A = A.”
“Excellent!” said Griffin.
“Since A1A = A,” continued Craig, “then for any bird y, A1Ay = Ay. But also, A1Ay = yA(AyA), because for any bird x, A1xy = yx(xyx). Since A1Ay = yA(AyA) and also A1Ay = Ay, then Ay = yA(AyA). This solves the problem.”
“Great!” exclaimed Griffin. “But I am curious as to the second method you had in mind—the method that ‘proceeds from scratch.’ What method is that?”
“Well,” replied Craig, “in the expression yx(xyx), just replace x by (xx), thus obtaining the expression y(xx)((xx)y(xx)). Then there is a bird A2 such that for any birds x and y, A2xy = y(xx)((xx)y(xx)). Then, taking A2 for x, A2A2y = y(A2A2)((A2A2)y(A2A2)). And then we take for A the bird A2A2, and so Ay = yA(AyA).”
“Ah, yes!” said Griffin.
“Actually,” said Craig, “I imagine the first method would, in general, yield a much shorter expression for A. The prospect of finding an x-y-eliminate of the expression y(xx)((xx)y(xx)) strikes me as pretty grim compared to finding an x-y-eliminate of the expression yx(xyx). So in practice, I think I would use the first method.
“Of course, the same method—either one, in fact—works for your second problem. To find a bird A satisfying the condition that Ayz = (z(yA))(yAz), let A1 be an x-y-z-eliminate of the expression (z(yx))(yxz), and let A be the bird LA1(LA1). Then A1A = A, so A1Ayz = Ayz, so Ayz = A1Ayz = (z(yz))(yAz), and A is the desired bird.
“The same method would work for any expression with four variables instead of three. For example, take the expression x(zwy)(xxw). If we let A1 be an x-y-z-w-eliminate of this expression and let A be the bird LA1(LA1), then for any birds y, z, w, Ayzw = A(zwy)(AAw). Indeed, the same method would work for any expression with any number of variables. Is this the principle you call the fixed point principle?”
“You have the idea,” said Griffin. “To state the fixed point principle in its most general form, suppose we take any number of variables x, y, z … and write down any equation of the form Axyz … = (—–), where (—–) is any expression built from these variables and the letter A. For example, (—–) might be the expression yA(wAA)(xAz). The fixed point principle is that the equation can always be solved for A—in other words, there is a bird A such that for any birds x, y, z … it is true that Axyz … = (—–). In the above example, there is a bird A such that for any birds x, y, z, w it is true that Axyzw = yA(wAA)(xAz). You will see the importance of this principle when we come to the study of arithmetical birds.
“I might remark,” added Griffin, “that the existence of a sage bird is only a special case of the fixed point principle—the case where (—–) is the expression x(Ax). By the fixed point principle, there is then a bird A such that for every bird x, Ax = x(Ax)—such a bird A is a sage bird.”
“That’s interesting!” said Craig. “I hadn’t seen a sage bird in that light before.”
The following exercises should give the reader further insight into the uses of the fixed point principle.
Exercise 1 (Sage birds revisited): Let us look again at the problem of finding a sage bird A—only now from the point of view of the fixed point principle.
We are to find a bird A satisfying the equation Ax = x(Ax)—for all birds x. In this chapter, we have seen two different methods of solving such an equation. Try both methods and see what birds you get. Both of them have been encountered in Chapter 13.
Exercise 2 (Commuting birds revisited): Using both methods, find a bird A such that for every bird x, Ax = xA. Such a bird A commutes with every bird x (recall Problem 18, Chapter 11). One of the solutions will be the same as that of Problem 18, Chapter 11; the other solution will be new. What new solution do you get?
Exercise 3: In each case, find a bird A satisfying the given requirement. (Better use the first method.)
a. Ax = Axx
b. Ax = A(xx)
c. Ax = AA(xx)
Exercise 4: Find a bird A such that for every bird x, Ax = AA.
Exercise 5: In each case, find a bird A satisfying the given requirement.
a. Axy = xyA
b. Axy = Ayx
c. Axy = x(Ay)
Exercise 6: By the fixed point principle, there is a bird A such that for any birds x, a, and b, Axab = x(Aaab)(Abab). Using this fact, prove the following theorem (known as the double fixed point theorem): For any birds a and b there are birds c and d such that acd = c and bcd = d. This constitutes a new and quite simple proof of the double fixed point theorem.
SOLUTIONS
Ex. 1: Using the first method, we must first find a bird A1 such that for all x and y, A1yx = x(yx), and any bird of which A1 is fond will be a solution. Well, the owl O is such a bird A1, and LO(LO)—or any other bird of which O is fond—is a sage bird. We thus get the same solution as we got in Problem 14, Chapter 13.
Using the second method, we must first find a bird A1 such that for all x and y, A1yx = x(yyx), and then A1A1 will be a solution. Well, the Turing bird U is such a bird A1, and so we see again that our old friend UU is a sage bird.
Ex. 2: Using the first method, you should get LT(LT)—or any other bird of whom the thrush T is fond—as a solution. This is the same as Problem 18, Chapter 11.
Using the second method, you should get the solution W’W’, where W’ is the converse warbler—W’xy = yxx. If you get CW(CW) you are also right, since CW is a converse warbler. You can easily check that W’W’x = x(W’W’).
Ex. 3:
a. LW(LW)
b. LL(LL)
c. L(LL)(L(LL))
Ex. 4: Some of you may have been stumped by this, since A is the only letter on the righthand side of the equation. However, either method still works; we will use the first.
We must first find a bird A1, such that for every x and y, A1yx = yy. Well, BKM is such a bird, as you can easily check, and so L(BKM)(L(BKM)) is a solution.
Ex. 5:
a. LR(LR)
b. LC(LC)
c. LQ(LQ)
Ex. 6: For any birds x, a, and b, Axab = x(Aaab)(Abab). Therefore, if we take a for x, we see that Aaab = a(Aaab)(Abab). If, instead, we take b for x, we see that Abab = b(Aaab)(Abab). Therefore, if we let c = Aaab and d = Abab, we see that c = acd and d = bcd.
22
A Glimpse into Infinity
SOME FACTS ABOUT THE KESTREL
“You know,” said Griffin to Craig, in another of their daily chats, “despite the fact that Professor Bravura dislikes the ‘lowly’ kestrel, this bird has some interesting properties.”
• 1 •
“For example,” continued Professor Griffin, “suppose we have a bird forest in which there are at least two birds. You know that a kestrel cannot be fond of itself?”
“I remember that,” replied Craig. He was thinking of Problem 19, Chapter 9.
“Did you know that if the forest contains at least two birds, then it is impossible for a kestrel to be fond of an identity bird?”
“I never thought about that,” said Craig.
“The proof is quite easy,” remarked Griffin.
What is the proof?
>
• 2 •
“I hate these silly forests having only one bird,” said Griffin. “In all the problems I will give you today, I am making the underlying assumption that the forest has at least two birds.
“Prove that if K is a kestrel and I is an identity bird, then I ≠ K—in other words, no bird can be both an identity bird and a kestrel.”
• 3 •
“Another thing,” said Griffin: “No starling can be fond of a kestrel. Can you see why this is so?”
• 4 •
“It follows from this,” continued Griffin, “that no starling can also be an identity bird. Can you see why?”
• 5 •
“I see now,” said Craig, “that no bird can be both a starling and an identity bird and no bird can be both a kestrel and an identity bird. Is it possible for a bird to be both a starling and a kestrel?”
“Good question!” said Griffin. “The answer is not difficult to figure out.”
What is the answer? Remember, we are assuming that the forest contains at least two birds.
• 6 •
“Here is a simple but important principle,” said Griffin. “You have already agreed that no kestrel K can be fond of itself. This means that KK ≠ K. This fact can be generalized: For no bird x is it the case that Kx = K! Can you prove this?”
Note: It will be helpful to the reader to recall the cancellation law for kestrels, which we proved in Chapter 9, Problem 16—namely, that if Kx = Ky, then x = y.