To Mock a Mocking Bird
Page 12
12 • Turing Birds and Sage Birds
The remarkable thing about the Turing bird U is that from U alone you can derive a sage bird—moreover, you can do it in as simple and direct a manner as can be imagined. Can you see how?
Some open problems: We now see that a sage bird can be derived from just one proper combinator—Turing’s bird U. Of course, U is not regular. Can a sage be derived from just one regular combinator? I tend to doubt it, but I cannot prove that the answer is negative. Can a sage be derived from B and one other regular combinator? This is another question I have not been able to answer. As far as I know, these two problems are open, though I haven’t checked the literature sufficiently to be sure of this.
OWLS
13 • Owls
An extremely interesting bird is the owl O defined by the following condition:
Oxy = y(xy)
Show that an owl can be derived from B, C, and W—in fact, from just Q and W.
• 14 •
A sage bird can be derived from O and L. Better yet, a Turing bird is derivable from O and L. How?
• 15 •
Show that a mockingbird is derivable from O and I.
• 16 •
Show that O is derivable from S and I.
WHY OWLS ARE SO INTERESTING
17 • A Preliminary Problem
Preparatory to the next problem, prove that if a bird x is fond of a bird y, then x is fond of xy.
• 18 •
An interesting thing about owls is this: If you call out a sage bird to an owl, the owl will always respond by naming a sage bird—either the same sage bird or a different one. In other words, for any sage bird Ө, the bird OӨ is also a sage bird. Prove this.
• 19 •
Another interesting thing about owls is that if you call out an owl to a sage bird, the sage bird will respond by naming a sage bird. In other words, for any sage bird Ө and any owl O, ӨO is a sage bird. Prove this.
• 20 •
Equally if not more interesting is the fact that an owl is fond only of sage birds! In other words, for any bird A, if OA = A, then A must be a sage bird. Prove this.
• 21 •
The last problem has as a corollary a fact that generalizes the result of Problem 19. Let us say that a bird A is choosy if it is fond only of sage birds. All owls are choosy, according to the last problem, but there may be other choosy birds. Now let Ө be a sage bird. Prove that it is not only the case that ӨO is a sage, as in Problem 19, but that for any choosy bird A, the bird ӨA must be a sage.
22 • Similarity
A bird A1 is said to be similar to a bird A2 if A1 and A2 respond the same way to any bird x—in other words, for every bird x, A1x = A2x. As far as their responses to birds are concerned, similar birds behave identically.
We proved in Problem 18 that for any sage bird Ө, the bird OӨ is also a sage, but we didn’t prove that OӨ is necessarily the same bird as Ө. However, OӨ can be proved to be similar to Ө. How?
Remarks: A bird forest is called extensional if no two distinct birds are similar—in other words, if for any birds A1 and A2, if A1 is similar to A2, then A1 = A2. Extensional forests might also be called sparse, since it easily follows from the extensional condition that there cannot be more than one identity bird, one mockingbird, one cardinal, one starling, and so forth.
Although the subject of extensionality is an important one, we will not be treating it in this volume. There is one fact, though, that I believe will interest you: In an extensional forest, an owl is fond of all sage birds! Do you see how to prove this?
I hope you see the ramifications of this! This fact, together with Problem 20, implies that an owl is fond of sage birds and no other birds. Thus, if you go over to an owl O and call out the name of a bird x, if O responds by calling back x, then x is a sage bird; if O calls back some bird other than x, then x is not a sage bird. So, in an extensional forest, owls seem to somehow know which birds are sage birds and which ones are not. Is this not wise of them?
• 23 •
Prove that in an extensional forest, an owl is fond of all sage birds.
SOLUTIONS
1 · Our starting point is that any bird x is fond of the bird M(BxM), as we proved in the solution of Problem 2 of Chapter 11. And so our present problem reduces to finding a bird Ө such that for any bird x, Өx = M(BxM).
Well, BxM = RMBx (R is the robin), so M(BxM) = M(RMBx) = BM(RMB)x. And so we can take Ө to be BM(RMB).
Let us double-check that BM(RMB) really is a sage bird: For any bird x, BM(RMB)x = M(RMBx) = RMBx(RMBx) = BxM(RMBx) = x(M(RMBx)). Since M(RMBx) = BM(RMB)x, then x(M(RMBx)) = x(BM(RMB)x). Therefore BM(RMB)x = x(BM(RMB)x)—they are both equal to BxM(RMBx)—and so BM(RMB) is a sage.
2 · BxM = RMBx, but also BxM = CBMx, and so M(BxM) = M(CBMx) = BM(CBM)x. Since x is fond of M(BxM) and M(BxM) = BM(CBM)x, then x is fond of BM(BCM)x, and so BM(CBM) is also a sage bird.
3 · We proved in Problem 25 of Chapter 9 that x is fond of Lx(Lx), where x is any bird. Now, Lx(Lx) = M(Lx) = BMLx. Hence x is fond of BMLx, which makes BML a sage bird!
Incidentally, this provides an alternative proof for the results of the last two problems:
For any lark L, the bird BML is a sage. Now, CBM is a lark, according to Problem 2 of the last chapter, hence BM(CBM) is a sage, which again solves Problem 2. Also RMB is a lark, according to Problem 2 of the last chapter, and so BM(RMB) is a sage, which again solves Problem 1.
4 · Since BWB is also a lark, according to Problem 3 of the last chapter, then by the above problem, BM(BWB) is a sage bird.
5 · We will defer the solution till after the next problem.
6 · Again we use the important fact that x is fond of Lx(Lx). Now, Lx(Lx) = QL(Lx)x. Also, QL(Lx) = QL(QL)x, hence QL(Lx)x = QL(QL)xx, and so Lx(Lx) = QL(QL)xx. Furthermore, QL(QL)xx = W(QL(QL))x. This proves that Lx(Lx) = W(QL(QL))x, and since x is fond of Lx(Lx), then x is fond of W(QL(QL))x, which means that W(QL(QL)) is a sage bird.
7 · If in the above expression we take BC for Q, we get W(CBL(CBL)), which can be shortened to W(B(CBL)L). We can then take BWB for L, thus getting the expression W(B(CB(BWB))(BWB)).
Another solution will result from a later problem.
8 · Again we use the fact that x is fond of Lx(Lx), and therefore x is fond of M(Lx). Now, M(Lx) = QLMx, so x is fond of QLMx, which means that QLM is a sage bird.
We can now take QM for L, because QM is a lark, as we showed in Problem 4, Chapter 12. We thus get the expression Q(QM)M. And so Q(QM)M is a sage bird, as the reader can verify directly.
9 · It is also the case that Lx(Lx) = SLLx, and so SLL is a sage bird.
10 · We just showed that SLL is a sage. Also SLL = WSL and so WSL is a sage. Since BWB is a lark, we can take BWB for L, thus getting WS(BWB).
This is Curry’s expression for a fixed point combinator.
Note: We know that B(BW)(BBC) is a starling, from Problem 12, Chapter 12, and so we can take this expression for S in WS(BWB), thus getting W(B(BW)(BBC))(BWB). This is another expression for a sage in terms of B, C, W, and so we have another solution to Problem 5.
11 · There are many ways of going about this. Here is one. Since the forest contains B, T, and M, it also contains W, L, and Q. Now, y(xxy) = Q(xx)yy = LQxyy = W(LQx)y = BW(LQ)xy. We can therefore take U to be BW(LQ).
12 · For all x and y, Uxy = y(xxy), or what is the same thing, for all y and x, Uyx = x(yyx). We take U for y and we see that UUx = x(UUx). Therefore UU is a sage bird.
13 · y(xy) = Byxy = CBxyy = W(CBx)y = BW(CB)xy. We can therefore take O to be BW(CB).
Also, y(xy) = Qxyy = W(Qx)y = QQWxy, and so QQW is also an owl.
14 · LO is a Turing bird, since LOxy = O(xx)y = y(xxy). And so also LO(LO) is a sage bird.
15 · OIx = x(Ix) = xx, so OI is a mockingbird.
16 · SIxy = Iy(xy) = y(xy), so SI is an owl.
17 · Suppose x is fond of y. Then xy = y. Since x is fond of y and y = xy, then x is fond of xy.
&n
bsp; 18 · Suppose Ө is a sage bird; we are to show that OӨ is a sage bird.
Take any bird x. Then x is fond of Өx, since Ө is a sage. Therefore, by the last problem, x is fond of x(Өx). But x(Өx) = OӨx, and so x is fond of OӨx. Therefore OӨ is a sage bird.
19 · Suppose Ө is a sage. Then for any bird y, Өy = y(Өy), so in particular, ӨO = O(ӨO). Then for any bird x, ӨOx = O(ӨO)x = x(ӨOx). So ӨOx = x(ӨOx), or equivalently, x(ӨOx) = ӨOx, which means that x is fond of ӨOx. Therefore ӨO is a sage.
20 · Suppose OA = A. Then A = OA, hence for any bird x, Ax = OAx = x(Ax). Since Ax = x(Ax), x is fond of Ax, and so A is a sage.
21 · Suppose A is choosy and Ө is a sage. Since Ө is a sage, then A is fond of ӨA. But since A is fond only of sages, then ӨA must be a sage.
22 · Suppose Ө is a sage. Then for every bird x, Өx = x(Өx). Also OӨx = x(Өx). Therefore OӨx = Өx, since both are equal to x(Өx). Therefore OӨ is similar to Ө.
23 · Suppose the forest is extensional. Now suppose Ө is a sage. By the last problem, OӨ is similar to Ө, and since the forest is extensional, then OӨ is the bird Ө. Thus OӨ = Ө, which means that O is fond of Ө. And so in an extensional forest, O is fond of all sage birds.
PART FOUR
SINGING
BIRDS
14
Curry’s Lively Bird Forest
When Inspector Craig reached Curry’s Forest, the first thing he did was to interview the resident bird sociologist, whose name, curiously enough, was Professor Byrd.
“In this forest,” said Byrd, “certain birds sing on certain days. It has been my purpose to determine which birds sing on which days. So far, I have not been able to come to a definite solution. I have been looking for one unifying principle—one general law that would enable me to decide which birds sing on which days. Over a period of many years I have gathered an enormous amount of statistical data; I have amassed tens of thousands of facts, and aided by a high-speed computer, I have been able to amalgamate all these facts into four general laws. These four laws give me partial information, but I cannot see how I can determine from them exactly which birds sing on which days. I have the feeling that there should be just one general law that would unify these four laws—much as Newton’s universal law of gravitation unified Kepler’s three laws of planetary motion. But I have not been able to find it. I wonder if you could help me.”
“I’ll do what I can,” said Craig. “What are the four laws?”
“Well, we have here a very special bird P. I do not know its species, nor does it matter. The important thing is that for any bird x and any bird y, whether the same as x or different, the following laws hold:
Law 1: If y sings on a given day, then Pxy sings on that day.
Law 2: If x doesn’t sing on a given day, then Pxy sings on that day.
Law 3: If the bird x and the bird Pxy both sing on a given day, then y sings on that day.
Law 4: For every bird x there is a bird y such that y sings on those and only those days on which Pyx sings.
“Those are my four laws,” said Byrd. “Can you unify them into one grand law?”
“I’ll have to think about it,” said Craig, rising. “I’ll be back tomorrow and tell you if I’ve found anything significant.”
Craig went back to the inn in which he was staying and devoted some time to the matter. At one point he burst out laughing. “What a ridiculously simple law!” thought Craig. “How could Byrd have overlooked it all these years? I think tomorrow I’ll have a bit of fun with him.”
Craig visited Byrd the next day.
“I’ve solved your problem,” said Craig. “From your four laws I have been able to deduce one very general law, which in turn easily explains why the four particular laws are true.”
“Wonderful!” cried Byrd. “What is this general law?”
“Rather than tell you outright, I’ll give you a hint. It follows from your laws that all sparrows here sing on Tuesdays.”
“Amazing!” cried Byrd. “It so happens that all sparrows here do sing on Tuesdays, but how could you have deduced this from what I have told you? I haven’t said anything about sparrows or Tuesdays; what’s so special about sparrows and Tuesdays?”
“Nothing special about either,” replied Craig, “and this very fact should give you a hint as to what my general law is.”
Byrd sank back in puzzled thought.
“Don’t tell me,” he said at last, “that all birds here sing on all days!”
“Exactly!” said Craig.
“Fantastic!” cried Byrd. “Why didn’t this possibility ever occur to me before? But I still don’t completely understand. Why does it follow from the four laws I have given you that all birds here sing on all days?”
• 1 •
Why does it follow?
• 2 •
Suppose we are given Byrd’s first three laws, but instead of Byrd’s fourth law, we are given that the forest contains a lark. Does it then follow that all the birds sing on all days? Suppose that instead of being given a lark, we are given that there is a cardinal; would it then follow that all the birds sing on all days? Suppose we are given both a lark and a cardinal; does it then follow that all the birds sing on all days?
• 3 •
Again suppose we are given Byrd’s first three laws, but we are not given the fourth. Can you find a single combinatorial bird whose presence would imply that all the birds sing on all days?
Discussion (to be read after the reader has gone through the solutions of the last three problems): The above problems are all closely related to a famous result known as Curry’s paradox. Suppose that instead of talking about birds, we talk about propositions. And suppose that instead of talking about a bird singing or not singing on a given day, we talk about a proposition being true or false; every proposition is one or the other, but not both. For any proposition x and y, let Pxy be the proposition that either x is false or y is true, or what is the same thing, if x is true, then so is y. Then Byrd’s first three laws correspond to the following three elementary laws of logic:
Law 1: If y is true, then Pxy is true.
Law 2: If x is false, then Pxy is true.
Law 3: If x and Pxy are both true, so is y.
Law 1 says that if y is true, then either x is false or y is true, which is obvious, because if y is true, then regardless of whether x is true or false, at least one of the propositions x and y is true—namely y. Law 2 says that if x is false, then either x is false or y is true; this is again obvious. As to Law 3, suppose x and Pxy are both true. Since Pxy is true, then either x is false or y is true. The first alternative—x is false—doesn’t hold, since x is true, so the second alternative must hold—y is true.
Now, suppose we add the following law, which corresponds to Byrd’s fourth law:
Law 4: For any proposition x there is a proposition y such that the proposition y and the proposition Pyx are either both true or both false. That is, the bird y and the bird Pyx either both sing or both do not sing on a given day.
What happens if we add Law 4 to the other three laws of logic? We then get a paradox, because from the four laws 1, 2, 3, and 4 we can prove that all propositions are true, in exactly the same way as we proved from Byrd’s four laws that all the birds sing. Obviously it is not the case that all propositions are true, and so the addition of Law 4 to the other three laws creates an absurdity. This is Curry’s paradox.
It should be pointed out that Byrd’s four laws as applied to birds, which Byrd did, doesn’t create any paradox; it merely leads to the conclusion that all birds of the forest sing on all days, and there is no reason why this can’t be. It is only when the four laws are applied—or, I should say, “misapplied”—to propositions in the way indicated above that a genuine paradox arises.
Suppose we now consider an arbitrary collection of entities called objects, and suppose we have a certain operation which applied to object x and object y yields a certain object xy. We then have what is call
ed an applicative system, in which the object xy is called the result of applying x to y. We have been studying applicative systems for the last several chapters; our “objects” were birds and we took xy to be the response of x to y. Combinatory logic studies applicative systems with certain special properties, among which is the existence of various combinators, including C, which we have called a cardinal, and L, which we have called a lark. Now, suppose the “objects” we are studying include all propositions, both true and false, as well as other objects, the combinators. Suppose we have an object P such that for any proposition x and y, the object Pxy is the proposition that either x is false or y is true. If x and y are not both propositions, then Pxy is still a well-defined object and may or may not be a proposition, depending on the nature of x and y. Laws 1, 2, and 3, of course, hold, provided x and y are propositions! Also, assuming C and L are present, given any object x, there must be an object y such that y = Pyx, as we saw in the solution to Problem 2. In particular, given any proposition x there must be an object y such that y = Pyx, but this y needn’t be a proposition! In fact, y can’t be a proposition, because if it were, Pyx would also be a proposition and the same proposition as y, which would mean that Law 4 would hold and we would again run into Curry’s paradox. So the way out of the paradox is to realize that given a proposition x, although the axioms of combinatory logic imply that there is some object y such that y = Pyx, such a y cannot be a proposition. Some of the earlier systems, which attempted to combine the logic of propositions with combinatorial logic, were careless on this point and so the systems turned out to be inconsistent. But, as Haskell Curry pointed out, the paradoxes were not the fault of combinatory logic itself, they were the result of the misapplication of combinatory logic to the logic of propositions.