Next we need an expression X2 whose only variable is x such that the relation X2y = S(Kx)y holds. Here we have unexpected luck, since we can take X2 to be S(Kx). Note: The expression S(Kx)y is already in the form X2y, if y is not a variable of X2. We are not often that lucky!
Finally, we need an expression X3 with no variables at all such that the relation X3x = S(Kx) holds. Well, since KS is an expression such that KSx = S and K is an expression such that Kx = Kx, then S(KS)K is the expression X3 that we seek. Check: S(KS)Kx = KSx(Kx) = S(Kx). Therefore S(KS)K must be a bluebird, as the reader can check by showing that S(KS)Kxyz = x(yz).
We have by now pretty well illustrated the general method, which is this: Our expressions are built from the letters S, K, I, and variables x, y, z, w, v, and any others we might need. Let α stand for any one of the variables. For any expression X, call an expression X1 an α-eliminate of X if the following two conditions hold:
1. The variable α does not occur in X1.
2. The relation X1α = X must hold. By this I do not mean that X1α is necessarily the expression X, but only that the equation X1α = X is derivable from the defining conditions of S and K. For example, “KKα” and “K” are different expressions, but the relation KKα = K does hold, by virtue of the defining condition of the kestrel—namely that for any x and y, Kxy = x.
The fundamental problem, then, is this: Given an expression X and a variable α, how do we find an α-eliminate of X? This can always be done by a finite number of applications of the following four principles:
Principle 1: If X consists of just the variable α standing alone, then I is an α-eliminate of X. Stated otherwise, I is an α-eliminate of α. Reason: The variable α is obviously not part of the expression I and Iα = α does hold. Therefore I satisfies both the conditions of being an α-eliminate of α.
Principle 2: If X is an expression in which the variable α doesn’t even occur, then KX is an α-eliminate of X. The reason is obvious: Since α doesn’t occur in X, then it doesn’t occur in KX and the relation KXα = X holds.
Principle 3: If X is a composite expression Yα and α doesn’t occur in Y, then Y itself is an α-eliminate of X. Stated otherwise, if α doesn’t occur in Y, then Y is an α-eliminate of Yα. The reasons are obvious. As an example, yz is an x-eliminate of yzx, since x doesn’t occur in yz and yz is an expression E such that Ex = yzx. Also KyI is an x-eliminate of KIyx, but KIy is not a y-eliminate of KIyx!
Principle 4: Suppose X is a composite expression YZ, and that Y1 is an α-eliminate of Y, and Z1 is an α-eliminate of Z. Then the expression of SY1Z1 is an α-eliminate of X. Reason: The relations Y1α = Y and Z1α = Z both hold, by hypothesis, and the relation SY1Z1α = Y1α(Z1α) holds, hence the relation SY1Z1α = YZ = X holds. Also α doesn’t occur in Y1 or in Z1—by hypothesis that Y1 and Z1 are respectively α-eliminates of Y and Z—hence α doesn’t occur in SY1Z1. Hence SY1Z1 is an expression X1 in which α doesn’t occur and which has the property that the relation X1α = X must hold.
We note that Principle 4 reduces the problem of finding an α-eliminate of a complex expression YZ to the problem of finding α-eliminates of each of the shorter expressions Y and Z. To find one or both of these, you might have to use Principle 4 again, and perhaps again and again, but since the expressions involved are getting shorter and shorter, the process must finally terminate.
Let us consider some examples. Suppose we wish to find an x-eliminate of the expression yx(xy). In unabbreviated notation, the expression is (yx)(xy). We see that Principle 4 is the only one that is immediately applicable, and so we must first find an x-eliminate of yx and an x-eliminate of xy. Well, by Principle 3, y is an x-eliminate of yx. As to xy, we must again use Principle 4: Since I is an x-eliminate of x and Ky is an x-eliminate of y, then by Principle 4, SI(Ky) is an x-eliminate of xy. So y is an x-eliminate of yx and SI(Ky) is an x-eliminate of xy; therefore, by Principle 4, Sy(SI(Ky)) is an x-eliminate of yx(xy). The reader can check that Sy(SI(Ky))x = yx(xy).
On the other hand, suppose we wanted to find a y-eliminate of (yx)(xy). We must first find a y-eliminate of yx and a y-eliminate of xy. As to the former, since I is a y-eliminate of y and Kx is a y-eliminate of x, then SI(Kx) is a y-eliminate of yx. As to the latter, x is a y-eliminate of xy. So SI(Kx) is a y-eliminate of yx and x is a y-eliminate of xy, hence, by Principle 4, S(SI(Kx))x is a y-eliminate of yx(xy). The reader can check that the relation S(SI(Kx))xy = yx(xy) must hold.
Now that we know how to find an α-eliminate of X, for any variable α and any expression X, we can derive from S, K, and I any combinator to do any required job. If X has only one variable—say x—and we wish to find a combinator A such that the relation Ax = X holds, we take for A any x-eliminate of X. Example: Suppose we want a combinator A such that the relation Ax = x(xx) holds. Well, I is an x-eliminate of x, so SII is an x-eliminate of xx. Since I is an x-eliminate of x and SII is an x-eliminate of xx, then SI(SII) is an x-eliminate of x(xx). So a combinator A that works is SI(SII), as the reader can check.
Suppose we have an expression X involving two variables—say x and y—and we seek a combinator A such that the relation Axy = X holds. We first find a y-eliminate of X—call it X1—and then we find an x-eliminate of X1—call it X2, so X2 is the combinator we seek. As an example, suppose we want a combinator A such that for any x and y, Axy = yx(xy). Well, we have already found a y-eliminate of yx(xy)—namely S(SI(Kx))x. We must then find an x-eliminate of S(SI(Kx))x. We can arrange our work as follows:
1. K(SI) is an x-eliminate of SI.
2. K is an x-eliminate of Kx.
3. Therefore S(SI)K is an x-eliminate of SI(Kx).
4. KS is an x-eliminate of S.
5. Hence, according to steps 4 and 3 and Principle 4, S(S(KS)(S(SI)K))I is an x-eliminate of S(SI(Kx))x and is a
6. I is an x-eliminate of x.
7. Therefore, according to steps 5 and 6 and Principle 4, S(S(KS)(S(SI)K)) I is an x-eliminate of S(SI(Kx))x and is a combinator A doing the required job that Axy = yx(xy), as the reader can verify.
In short, if X is an expression in just two variables x and y, a combinator A that works for X—by which we mean that the relation Axy = X holds—is obtained by finding an x-eliminate of a y-eliminate of X—such an expression we call an x-y-eliminate of X. If X contains three variables x, y, and z, we find A by finding an x-eliminate of a y-eliminate of a z-eliminate of X—such an expression we call an x-y-z-eliminate of X. We have already done this for the expression x(yz), when we derived the bluebird.
Let us conclude with another example—finding a queer bird. Of course, we have already derived B and T from S and K, and in an earlier chapter we derived Q from B and T, but let us forget that we know this and see how to derive Q directly from S, K, and I.
The expression X is now y(xz). I will condense some of the steps. Thus, Ky is a z-eliminate of y; x is a z-eliminate of xz, so S(Ky)x is a z-eliminate of y(xz). Now we must find a y-eliminate of S(Ky)x. Well, S(KS)K is a y-eliminate of S(Ky)—I have condensed two steps—and Kx is a y-eliminate of x, so S(S(KS)K)(Kx) is a y-eliminate of S(Ky)x. Finally, we must find an x-eliminate of S(S(KS)K)(Kx). Well, an x-eliminate of S(S(KS)K) is K(S(S(KS)K)) and an x-eliminate of Kx is K, so S(K(S(S(KS)K))K) is an x-eliminate of S(S(KS)K)(Kx), and hence is a queer bird, as the reader can verify.
Of course, the procedure is applicable to an expression X with any number of variables. If X has four variables x, y, z, and w, we find the desired combinator by first finding the w-eliminate of X; then the z-eliminate of the result; then the y-eliminate of that result; and then the x-eliminate of that. Such an expression is called an x-y-z-w-eliminate of X. As an exercise, the reader should try to derive a dove D from S, K, and I. We recall that Dxyzw = xy(zw).
Some remarks are in order. First of all, the procedure we have described can be exceedingly tedious and often leads to much longer expressions than can be found by using cleverness and ingenuity. However, it is surefire, and is bound finally to result in the combinator you are seeking.
Secondly, it should be observed that the combinator you finally wind up with is not necessarily unique, because the method of finding α-eliminates can lead to several solutions, depending on the order in which you use the four principles. As an example, suppose we wish to find a z-eliminate of the expression xy. On the one hand, we can use Principle 2 and get K(xy) as a z-eliminate of xy. On the other hand, since Kx is a z-eliminate of x and Ky is a z-eliminate of y, then S(Kx)(Ky) is a z-eliminate of xy. Of course, the expression K(xy) is the simpler of the two, but K(xy) and S(Kx)(Ky) are both z-eliminates of xy, since K(xy)z = xy and also S(Kx)(Ky)z = Kxz(Kyz) = xy.
Another example: Suppose we want to find a y-eliminate of xy. On the one hand, x is a y-eliminate of xy, by Principle 3. On the other hand, since Kx is a y-eliminate of x by Principle 2 and I is a y-eliminate of y by Principle 1, then by Principle 4, S(Kx)I is also a y-eliminate of xy—a far more clumsy one than x, to be sure!
We see now that our process of finding an α-eliminate of an expression X is not deterministic; it can lead to more than one α-eliminate. It can be made completely deterministic by simply observing the following restriction: Never use Principle 4 if any of the other three principles is applicable!
With this restriction on the procedure, you can obtain only one α-eliminate of a given expression X. This deterministic procedure can be easily programmed on a computer, and those of you with home computers who like to work up software should find it an entertaining and profitable exercise to write a program to find combinators for any given expression.
19
Aristocratic Birds
Craig spent several weeks in the Master Forest and learned many interesting things from Professor Griffin.
“You seem to have known about many birds before you ever came here,” remarked Griffin in one of their daily chats. “Where did you learn about them?”
“I learned about most of them from a certain Professor Adriano Bravura. Have you heard of him?”
“Oh, heavens!” cried Griffin. “He was my teacher! I spent several years in his forest. That’s where I got my start.”
“Several things have puzzled me,” said Craig. “Professor Bravura showed me how to derive a large number of birds from just the four birds B, T, M, and I. Are all combinatorial birds derivable from these four birds?”
“Definitely not,” replied Griffin. “The kestrel K cannot be derived from B, T, M, and I.”
“Why is that?” asked Craig.
“This can be rigorously proved,” replied Griffin. “The essential idea behind the proof is this:
“The bird K has what is known as a cancellative effect in that Kxy = x. Look at the right side of the equation Kxy = x. What has happened to the bird y? It has mysteriously disappeared—maybe it has flown away! Anyway, we say that y has been canceled, and hence that K has a cancellative effect. Likewise the bird K2 obeying the condition K2xy = y is cancellative; the variable x has disappeared. I could name many more cancellative birds. Now, none of the birds B, M, T, and I are cancellative, and it is impossible to derive a cancellative bird from noncancellative birds. Therefore the cancellative bird K cannot be derived from B, T, M, and I.”
“That’s interesting,” said Craig, “and that reminds me of another thing that has puzzled me. I once asked Professor Bravura whether there were any kestrels in his forest. He seemed somewhat upset by the question and replied in a strained voice: ‘No! Kestrels are not allowed in this forest!’ I felt like asking him why, but the subject obviously upset him. Do you know anything about this?”
“Oh, yes,” said Griffin with a laugh. “You see, Bravura is somewhat of a purist and wants only aristocratic birds in his forest.”
“Now, what on earth do you mean by an aristocratic bird?” asked Craig, in amazement.
“I got the term from Bravura,” replied Griffin, still amused. “By an aristocratic bird, he simply means a combinatorial bird that is noncancellative.”
“Why the term ‘aristocratic’?” asked Craig.
“Well, you see, he is a bit eccentric in some of his ways. He comes from the ancient Italian nobility and has some rather old-fashioned aristocratic attitudes toward life. He regards any bird who ‘cancels out’ other birds as somehow lacking in nobility; he calls such birds common birds. The other birds he calls aristocratic birds.
“In a way, I can see his point,” continued Griffin, “though of course I allow common birds in my forest, since they have a valuable mathematical function. And yet, if I have my choice of deriving an aristocratic bird either from S and K or from the four aristocratic birds B, T, M, and I, I tend to favor the latter. I am always a little uncomfortable using a common bird to derive an aristocratic one.”
“Are all aristocratic birds derivable from B, T, M, and I?” asked Craig.
“Yes; there is a well-known recipe for deriving all aristocratic birds from B, T, M, and I—or more directly, from B, C, S, and I. I will show it to you sometime, if you like.”
Note: The recipe is given in the appendix to this chapter.
“One thing strikes me as curious,” said Craig. “From just two combinators—S and K—all combinators are derivable; yet we apparently need four aristocratic birds to derive all aristocratic birds. Why is this?”
“That’s actually not true,” replied Griffin. “It is true that of the four birds B, T, M, and I, no one of them is derivable from the other three. It is also true that of the four birds B, C, W, and I—which generate the same group as B, T, M, and I—none of them is derivable from the other three. It is also true that of the four birds B, C, S, and I—which again generate the same group as either of the other two foursomes—none of them is derivable from the other three. Nevertheless, there does exist a pair of aristocratic birds from which all aristocratic birds are derivable.”
“That’s interesting!” exclaimed Craig. “What are the two birds?”
“One of them is the identity bird I,” replied Griffin, “and the other is a bird that may not be familiar to you—it is the jaybird discovered by J. Barkley Rosser in 1935. The bird J is defined by the following condition:
Jxyzw = xy(xwz).”
“That is a curious bird!” said Craig. “You are right; I’m not familiar with it. Please tell me more about it.”
“Very well,” said Griffin. “I will first show you that J is derivable from B, T, M, and I—more directly, from B, C, W, and I. In fact, J is derivable from just B, C, and W. Then I will show you that B, T, and M are derivable from J and I. It will then follow that the class of birds derivable from J and I is the same as the class of birds derivable from B, T, M, and I.”
DERIVATION OF THE JAYBIRD
1 • Derivation of J
“There are several ways of deriving J from B, C, and W,” said Griffin. “Perhaps the simplest uses the eagle E, the bird C*—that is, the cardinal once removed—and the bird C**—that is, the cardinal twice removed. Try to derive J from E, C*, C**, and W. Then express J in terms of B, C, and W.”
GOING IN THE OTHER DIRECTION
“Now,” said Griffin, “we proceed in the opposite direction. We start with the two birds J and I and set out to derive B, T, and M. We will have to rederive several familiar birds along the way, and the order will be very different from that of the original derivations from B and T. For example, we will have to derive C before B, and before that we must derive—of all birds!—the quixotic bird Q1.”
2 • Derivation of Q1
“You recall the quixotic bird Q1, defined by the condition Q1xyz = x(zy). Show that a quixotic bird is derivable from J and I.”
3 • Derivation of the Thrush
“Next, derive a thrush T from Q1 and I.”
4 • Derivation of the Robin
“Next, from J and T, derive the robin R.”
5 • Derivation of the Bluebird
“Now that we have R,” said Griffin, “we can take C to be RRR, and so we have the cardinal. From C and Q1 we can now get the bluebird B. Do you see how?
&nbs
p; “Actually,” added Griffin, “the bird C* is easily derivable from C and Q1, and B is derivable from C* and Q1. This may be the easiest path.”
“Now we must derive the mockingbird,” said Griffin. “This is the trickiest and most interesting part. It will be helpful first to derive a relative of J.”
6 • The Bird J1
“From the three birds J, B, and T, derive a bird J1 satisfying the following condition:
J1xyzw = yx(wxz).”
7 • The Mockingbird
“And now the mockingbird is derivable from C, T, and J1. Show this.
“I’ll give you a hint,” added Griffin: “For any bird x, J1xTTT = xx. You can easily verify this.”
Griffin continued, “Now you see that the class of birds derivable from J and I is the same as the class of birds derivable from B, T, M, and I. If we started a bird forest with just the two birds J and I, we would ultimately get the same birds as if we had started with B, T, M, and I. The kestrel K would never appear, unless it flew in from another forest, nor would a whole host of birds derivable from S and K.”
Note: The theory of combinators derivable from B, T, M, and I—or equivalently from B, C, W, and I, or from just J and I—is technically known as the λ I-calculus. The theory of combinators derivable from S and K is known as the λK-calculus. Neither theory can be said to be “better” than the other; each has applications which the other does not.
SOLUTIONS
1 · xy(xwz) = Exyxwz = C*Exxywz = W(C*E)xywz = C**(W(C*E))xyzw. And so we can take J to be C**(W(C*E)).
In terms of B, C, and W, we have J = B(BC)(W(BC(B(BBB)))).
To Mock a Mocking Bird Page 15
