To Mock a Mocking Bird
Page 11
“We will occasionally have use for a bird W* satisfying the condition W*xyz = xyzz. How do you derive W* from B, T, and M? And what about a bird W** satisfying the condition W**xyzw = xyzww?”
10 • Warblers and Hummingbirds
“Another bird for which I have found use is the hummingbird H defined by the following condition:
Hxyz = xyzy
“Show that H is derivable from B, C, and W—and hence from B, M, and T.”
11 • Hummingbirds and Warblers
“You can also derive a warbler from B, C, and H—in fact, you can do it from C and H, and even more simply from R and H. Can you see how?”
STARLINGS
“I have been in this forest some time now,” said Craig, “and I have never seen a kestrel. Are there any kestrels here?”
“Absolutely not!” cried Bravura, in an unexpectedly fierce tone. “Kestrels are not allowed in this forest!!”
Craig was quite surprised at the severity of Bravura’s response and was on the verge of asking him why kestrels were not allowed, but he decided that the question might be tactless.
“Ah, there goes a starling,” Bravura said more brightly. “Tell me, are you planning to visit the Master Forest?”
“I was planning to visit Curry’s Forest,” replied Craig.
“And so you should!” replied Bravura. “But you shouldn’t stop there; you should continue on until you reach the Master Forest. You will pass through several other interesting forests along the way—before you leave, I’ll draw you a map. You will find your experience in the Master Forest to be a true education!”
“Then I’ll definitely go,” said Craig.
“Good!” replied Bravura. “But I should prepare you for your visit by telling you about the starling, since this bird plays a feature role in the Master Forest.”
12 • Starlings
“A starling,” said Bravura, “is a bird S satisfying the following condition:
Sxyz = xz(yz).”
“Why is that bird so important?” asked Craig.
“You will find that out when you reach the Master Forest,” replied Bravura.
“Anyway,” he continued, “you should know that a starling can be derived from B, T, and M—and more easily, from B, C, and W. The standard expression for S in terms of B, C, and W has seven letters, but I have discovered another having only six letters. It will be helpful to you to use the goldfinch G, which satisfies the condition Gxyzw = xw(yz). The starling S is easily derivable from B, W, and G.”
How is this done?
THE STARLING IN ACTION
“You have now seen that S is derivable from B, C, and W,” said Bravura. “It is also possible to derive W from B, C, and S. In fact, W is derivable from just C and S, or alternatively from R and S. I will also show you that W is derivable from T and S.”
13 • Hummingbirds Revisited
“You recall that the hummingbird H is defined by the condition Hxyz = xyzy. You have seen that H is derivable from B, C, and W. We now need to find out if a hummingbird is alternatively derivable from S and C—and even more simply from S and R. Is it?”
• 14 •
“Now write down an expression for a warbler in terms of S and R and one in terms of S and C.”
“You now see,” said Bravura, “that the class of birds derivable from B, C, and S is the same as the class of birds derivable from B, C, and W, since S is derivable from B, C, and W and W is derivable from C and S.”
• 15 •
“Since W is derivable from S and C, and C is derivable from B and T, then of course W is derivable from B, T, and S. However, W is derivable from just T and S. Can you show this?”
• 16 •
“Prove that M is derivable from T and S.”
“And now,” said Bravura, “you see that the class of birds derivable from B, T, and W is the same as the class of birds derivable from B, T, and S, since S is derivable from B, T, and W—it is even derivable from B, C, and W, and in the other direction, W is derivable from T and S. This class of birds is also the same as the class derivable from B, M, and T, since W is derivable from B, M, and T, and in the other direction, M is derivable from W and T, as you have seen.
“More important,” said Bravura, “is the fact that the class of birds derivable from B, T, M, and I is the same as the class of birds derivable from B, C, W, and I, since W is derivable from B, T, and M, and in the other direction, T is derivable from C and I—you recall that CI is a thrush. Either of these groups of four birds forms a basis for my forest, in the sense that every bird here is derivable from either of the foursomes. Alonzo Church preferred to take B, T, M, I as a basis; Curry preferred the basis B, C, W, I. Alternatively, we could use B, C, S, I as a basis, and for certain purposes this is technically convenient, but you will learn more about that when you reach the Master Forest.”
“I am starting out tomorrow,” said Craig, “and I am ever so grateful for all you have taught me. It should stand me in good stead in the journey ahead.”
“It certainly should,” said Bravura. “You have been a diligent student, and it has been a great pleasure to tell you some of the facts about birds I have learned. There are many more birds derivable from B, T, M, and I that I am sure would interest you. I think I will give you these derivations as exercises to take along with you to work out at your leisure. You will also encounter many other such birds in your travels ahead.
“Since you are making your journey on foot, it should take you about three days to reach Curry’s Forest. This forest is named after Haskell Curry, and appropriately so, since Curry was both an eminent combinatorial logician and an avid birdwatcher. After Curry’s Forest, you will come to Russell’s Forest—named for Bertrand Russell. Then you will come to another forest—let’s see now, I can never remember its name! Anyhow, next you will arrive at an extremely interesting forest named for Kurt Gödel. These four forests form a chain known as the Forests of Singing Birds. From Gödel’s Forest it should take you two days to reach the Master Forest. I wish you the best of luck!”
Here are some of the exercises that Bravura gave to Craig. Sketches of the solutions are given at the end of the chapter.
Exercise 1 (modeled on Church’s derivation of W):
a. From B and T, derive a bird G1 satisfying the condition G1xyzwv = xyv(zw).
b. From G1 and M, derive a bird G2 satisfying the condition G2xyzw = xw(xw)(yz).
c. From B, T, and I, derive a bird I2 such that for any bird x, I2x = xII.
d. Show that for any bird x, I2(Fx) = x, where F is a finch.
e. Now show that G2F(QI2) is a warbler. Note: Q is the queer bird.
Exercise 2 (the standard starling): The standard expression for a starling in terms of B, C, and W is B(B(BW)C)(BB). Show that this really is a starling.
Exercise 3: A phoenix is a bird Φ satisfying the condition Φxyzw = x(yw)(zw). The bird Φ is standard in combinatory logic. Show that Φ can be derived from S and B. This is tricky! An expression of only four letters works.
Exercise 4: A psi bird is a bird satisfying the condition xyzw = x(yz)(yw). The bird is also standard in combinatory logic. Show that is derivable from B, C, and W. Hint: Let H* be the bird BH. The bird is easily derivable from H* and the dovekie D2; remember that D2xyzwv = x(yz)(wv).
Exercise 5: It is a curious fact that is derivable from B, Φ, and—of all birds!—the kestrel K. We will divide this problem into two parts:
a. Show that from Φ and B we can get a bird Γ satisfying the condition Γxyzwv = y(zw)(xywv).
b. Show that is derivable from Γ and K.
Exercise 6: a. Show that from S and one bird already derived from B and T we can get a bird S’ satisfying the condition S’xyz = yz(xz).
b. Show that a warbler is derivable from S’ and the identity bird I.
Exercise 7: There is a bird derivable from Q alone such that CW is a starling. Can you find it? The expression for it has six letters.
SOLUTIONS
1 · xy(xy) = M(xy) = BMxy, and so we take M2 to be BM.
2 · x(yy) = x(My) = BxMy = CBMxy, and so CBM is a lark. Also, BxMy = RMBxy, and so RMB is also a lark.
We know that BBT is a robin R, and so BBTMB is a lark. Also BBTM = B(TM), and so B(TM)B is a lark. This gives a fairly simple expression for L in terms of B, T, and M.
3 · x(yy) = Bxyy = W(Bx)y = BWBxy. Therefore BWB is a lark.
4 · x(yy) = x(My) = QMxy, and so QM is a lark!
5 · M2R is a converse warbler, because M2Rxy = Rx(Rx)y = Rxyx = yxx.
In terms of B, M, and R, we can take W’ to be BMR. In terms of B, M, T, we can take W’ to be BM(BBT).
We could also take W’ to be B(BMB)T, as the reader can verify.
6 · CW’ is a warbler, because CW’xy = W’yx = xyy. In terms of B, M, C, R, we can take W to be C(BMR). This is Bravura’s expression for a warbler.
7 · We showed in Problem 22 of the last chapter that for any bird x, Cx = B(Tx)R. Therefore B(TW’)R is a warbler. If we take BM(BBT) for W’ and BBT for R, we get the expression B(T(BM(BBT)))(BBT); this expression is Bravura’s. We could alternatively take B(BMB)T for W’, thus getting B(T(B(BMB)T))(BBT); this is Rosser’s expression for a warbler.
8 · Yes; M can even be derived from W and T, because WTx = Txx = xx, and so WT is a mockingbird.
We now see that the class of birds derivable from B, T, and M is the same as the class of birds derivable from B, T, and W.
9 · Take W* to be BW and W** to be B(BW).
10 · xyzy = C*xyyz = W*C*xyz. We therefore take H to be W*C*. In terms of B, C, and W, H = BW(BC).
11 · From H and R we first derive the bird W’. Well, yxx = Rxyx = HRxy. Therefore HR is a converse warbler. Hence C(HR)—or alternatively R(HR)R—is a warbler.
12 · W**G is a starling because W**Gxyz = Gxyzz = xz(yz). So we take W**G for S, which in terms of B, C, and W is the expression B(BW)(BBC).
13 · Yes, it is. SR is a hummingbird, since SRxy = Ry(xy), hence SRxyz = Ry(xy)z = xyzy.
14 · Since SR is a hummingbird, then R(SRR)R is a warbler according to Problem 11. Also C(SRR) is a warbler, and so is C(S(CC)(CC)).
15 · This is particularly simple: ST is a warbler, since STxy = Ty(xy) = xyy.
16 · We have just seen that ST is a warbler. Also, for any warbler W, the bird WT is a mockingbird, as we saw in Problem 8. Therefore STT is a mockingbird.
SOLUTIONS TO THE EXERCISES
Ex. 1: a. Take G1 = BG.
b. Take G2 = G1(BM).
c. Take I2 = B(TI)(TI).
We leave the last two to the reader.
Ex. 2: Left to the reader.
Ex. 3: Take Φ = B(BS)B.
Ex. 4: Take = H*D2.
Ex. 5: a. Take Γ = Φ(Φ(ΦB))B.
b. Γ(KK) is a psi bird.
Ex. 6: a. Take S’ = CS.
b. S’I is a warbler.
Ex. 7: Take = Q(QQ(QQ))Q.
13
A Gallery of Sage Birds
While Inspector Craig is wending his way to Curry’s Forest, we will take time out to look at a medley of sage birds. But first I must tell you about combinatorial birds in general.
By a bird of order 1 is meant a bird A such that for any bird x, the bird Ax can be expressed in terms of x alone. For example, the mockingbird M is of order 1, since Mx = xx and the expression xx no longer involves the letter M; it is an expression in just the letter x. Another example is the identity bird I, since Ix = x. The birds M and I are the only birds of order 1 that we have so far encountered. Of course, we could construct from the birds of the last chapter an infinite variety of birds of order 1—for example, we might wish to consider a bird A such that Ax = x(xx). The bird WL would work. Or we could construct a bird A such that Ax = (x(xx))((xxx)x)—such a bird would also be of order 1.
By a bird of order 2 is meant a bird A such that Axy can be expressed in terms of just x and y. Examples are the thrush T, the lark L, and the warbler W; these three birds are obviously of order 2.
A bird of order 3 is a bird A whose definition involves three variables—say, x, y, z. Thus Axyz is expressible in terms of just x, y, and z. Most of the birds we have so far encountered are of order 3—the birds B, C, R, F, and V and the queer bird Q and its relatives Q1, Q2, Q3, Q4 are all examples of birds of order 3.
We similarly define birds of order 4, 5, 6, 7, 8, and so forth. Doves are of order 4; the bald eagle Ê is of order 7.
A bird having some order or other is called a proper combinatorial bird—or more briefly, a proper bird. By a combinatorial bird is meant any bird expressible in terms of proper birds. Not every combinatorial bird is proper. For example, the birds T and I are both proper; hence TI is a combinatorial bird, but it is not proper, for if it were, what order could it be? It isn’t of order 1, because TIx can be reduced to xI, but no further reduction is possible. TIxy can be expressed as xIy, but we haven’t got rid of I, so TI is not of order 2. The best we can do with TIxyz is to express is as xIyz, but the x is still in the way, so no further reduction is possible. No matter how many variables we tack onto the right of TIxyz, we can never get rid of I, so TI is not of any order; hence it is not a proper bird. On the other hand, IT is proper, since IT = T.
SOME SAGE BIRDS
We recall that by a sage bird is meant a bird Ө such that for any bird x, if one calls out x to Ө, then Ө will respond by naming a bird of which x is fond—in other words, x(Өx) = Өx (x is fond of Өx).
Sage birds are not proper birds! However, sage birds can be expressed in terms of proper birds; this can be done in a variety of ways that are quite fascinating. In Chapter 10 we never actually constructed a sage bird; we merely proved that if that forest obeyed certain conditions, then a sage bird must exist there. We shall now see how to find sage birds, given that certain proper birds are present.
• 1 •
Derive a sage bird from a mockingbird M, a bluebird B, and a robin R. This can be done using an expression of only five letters.
• 2 •
Find a five-letter expression for a sage bird in terms of B, C, and M.
• 3 •
A simpler construction of a sage bird uses a mockingbird, a bluebird, and a lark. Can you find it?
• 4 •
Derive a sage bird from a mockingbird, a bluebird, and a warbler.
• 5 •
A tougher job is to derive a sage bird from a bluebird, a cardinal, and a warbler. Care to try it? There are several ways in which this can be done, which will become apparent in the course of this chapter.
ENTER THE QUEER BIRD
We recall that the queer bird Q satisfies the condition Qxyz = y(xz). Thus Qxy composes y with x. Also Qxyz = Byxz. The queer bird is very useful in connection with sage birds.
• 6 •
Show that a sage bird is derivable from a queer bird, a lark, and a warbler.
• 7 •
Now can you see a way to solve Problem 5?
8 • Queer Birds and Mockingbirds
A particularly neat construction of a sage bird uses just the queer bird Q and the mockingbird M. Can you find it?
Discussion: By a regular combinator is meant a proper combinator such that, in its definition, the leftmost variable—say, x—of the left side of the equality is also the leftmost variable of the right side and occurs only once on the right side. For example, the cardinal is regular; Cxyz = xzy, and x is the leftmost variable of the right-hand side—xzy—and occurs only once in the expression xzy. On the other hand, the robin R is not regular; Rxyz = yzx, and x is not the leftmost variable of yzx. Also M is irregular, because x occurs twice in xx. The combinators B, C, W, L, S, I, and K are all regular; the combinators T, R, F, V, and Q are all irregular.
In each of the problems 1, 2, 3, 4, we derived a sage bird from three proper combinators; one was irregular, the mockingbird, and the other two were regular. In Problem 7 we derived a sage from three regular combinators. In Problem 8 we derived a sage from two irregular combinators, M and Q. We
will now see that a sage can be derived from just two regular combinators—moreover, in such a fashion that each of them is derivable from B, C, and W.
CURRY’S SAGE BIRD
9 • Starlings and Larks
Show that a sage bird can be derived from a starling S and a lark L.
10 • Curry’s Sage Bird
Now show that a sage bird can be derived from a bluebird, a warbler, and a starling. This can be done using an expression of only five letters.
Note: The solution of the above problem provides a second solution to Problem 5, since S can be derived from B, C, and W.
THE TURING BIRD
A bird deserving particular attention is the Turing bird U, defined by the following condition:
Uxy = y(xxy)
This bird was discovered by the logician Alan Turing in the year 1937, and is one of the most remarkable birds in existence! The reader will soon see why.
11 • Finding a Turing Bird
Before I tell you why I am such an admirer of the Turing bird, let’s see if you can find one, given the birds B, M, and T, and any birds derivable from them. Can you find a Turing bird?