For the next part in my Bean Machine retrospective to make sense I’ll need to make a short digression. In looking back on the almost 20 years I’ve been blogging, it is surprising to me that I’ve only briefly alluded to my appreciation of combinatory logic. In the next couple of episodes, I’ll do a quick introduction based on the delightful book that introduced it to me: To Mock A Mockingbird, by the late Raymond Smullyan.
Imagine a forest containing some birds, possibly finitely or infinitely many. These are unusual birds. When you call the species name of a bird in the forest to a bird in the forest, it calls one back to you. Maybe the same, maybe different, but when you tell a bird the name of a bird, it names a bird back to you. There might be a Red Capped Cardinal in the forest and when you call out Great Blue Heron to it, it calls back Belted Kingfisher.
(Photos by me; click for higher resolution.)
We will notate “I called Q to P and got response R” as PQ = R. If I then called out S to R and R responded with T, we’ll notate that as PQS = RS = T. We’ll use parentheses in the obvious way: PQS = (PQ)S and this might be different from P(QS). The latter is “I called S to Q, and then called Q‘s response to P“. I’ll use capital letters to represent specific bird names, and small letters to represent variables.
The question we’re considering here is: under what circumstances will a bird call back the same name you called to it? That is, for a given bird y, under what circumstances does yx = x?
Smullyan calls birds with this relationship “fondness” — that is, “y is fond of x” means that yx = x. If y is fond of x then x is said to be a “fixpoint” of y.
A forest is said to be “compositional” if for every pair of birds (a, b) — a and b can be the same or different — there is a bird c in the forest such that cx = b(ax) for all x. That is, if we call any name x to a, and then call its response to b, we get the same result as simply calling x to c. c is the composition of “call x to a, and then call that response to b“.
A mockingbird is the bird M with the property that Mx = xx. That is, for any bird name x, M tells you what x‘s response is to its own name. (The attentive reader will note that we have not said what MM is, but at least we know from the definition that MM = MM, so give me some credit for consistency at least.)
Theorem: if a compositional forest contains a mockingbird then every bird in the forest is fond of at least one bird.
Proof: Try to prove it yourself; scroll down for the solution.
.
.
.
.
.
.
.
Let p be any bird. Let c be the bird that composes p with M. Therefore cx = p(Mx) for all x.
In particular, that’s true for c, so cc = p(Mc). But Mc = cc, thus cc = p(cc), and we’ve found a bird that p is fond of. Since p was any bird, every bird in the forest is fond of at least one bird. Or, put another way, every bird in a compositional forest with a mockingbird has at least one fixpoint.
Next time on FAIC: we’ll take a look at a few more interesting birds, and then discuss why this whimsy is relevant to compilation before getting back to Bean Machine.
Fabulous adventures in coding 
Pingback: The Morning Brew - Chris Alcock » The Morning Brew #3626
This means the inverse must also be true: If a forest has at least one bird without a fixpoint, there can be no mockingbird in that forest. I can’t really wrap my head around this intuitively. I suppose it has to with how the mockingbird cannot “figure out” what the response of this fixpoint bird would be, but I can’t see why. Do you have any pointers for me to sort this out?
Looking at the inverse is a great idea. I’ll start in this comment by resolving a small point; we should state the inverse more carefully:
If a forest contains a bird without a fixpoint, then either (1) the forest is not compositional, or (2) the forest does not contain a mockingbird.
Consider a forest which contains exactly two birds, A and M, such that AA=M, AM=A, MA=M, MM=M. Plainly M is a mockingbird since Mx = xx for all x in the forest. And plainly A has no fixpoint. But this forest is not compositional! A compositional forest would contain a third bird C such that Cx = A(Mx), so CA=A, CM=A, and that bird is not in the forest.
I agree that the intuition around “if a *compositional* forest contains a bird without a fixpoint then there is no mockingbird in the forest” is harder to see. I’ll give it some thought.
Ah, yes it only holds for compositional forests.
Sometimes these things are just too far away from everyday life so our intuition has not been trained on it. I’m no mathematician either – if I were, maybe it would be more clear. In any case, thanks for a great blog!
All right, I’ve given it some thought for a few minutes. Let me try to pump your intuition with an example compositional forest where there is a *countable infinity* of birds in it. We’ll make a diagonalization argument.
Since there is a countable infinity of birds we can number them; that’s what countable means. And in fact we’ll just name the birds after their index; 0 is the first bird on the list, then 1, 2, 3, and so on. But these are still birds; you call out the name of a bird — a natural number — to one of them, and it calls back a natural number.
We could draw an infinite chart showing the name of the bird you call TO on the vertical axis and the name of the bird you give it on the horizontal axis:
0 1 2 ... ------- 0 | 9 8 5 ... 1 | 7 0 11 ... 2 | 6 9 3 ... ...So in this notation, 1 0 = 7, you get what I’m saying here I’m sure.
Now suppose one of those birds has no fixpoint. An easy example WOLOG would be the bird S such that S 0 = 1, S 1 = 2, S 2 = 3, and so on. The “successor bird”. (It has some index, but we don’t care what it is.)
Suppose there was a bird M on that list such that Mx = xx. What bird would that be? It would be the bird whose responses are on the *diagonal*. That is M 0 = 9, M 1 = 0, M 2 = 3, and so on.
Assume M is in the forest and deduce a contradition.
M is in the forest and therefore a bird C such that Cx = S(Mx) is also in the forest.
OK… so what is the index of C? It’s not 0, because C 0 = 10, not 9. It’s not 1, because C 1 = 1, not 0. It’s not 2 because C 2 = 4, not 3. And so on. C has no index, and therefore is nowhere on the list! But that’s a contradiction, and therefore M is not in the forest.
I hope that helps get your intuition around how powerful birds like M are.
It’s pretty easy to see how this generalizes to any function without a fixpoint; it doesn’t have to be the successor function. It’s maybe a little harder to see how it generalizes to forests with uncountably many birds, but hopefully that gives some of the flavor of the argument.
Yes, I think this is a good path to understanding it, thanks. I’ll have to read it a couple of additional times though. Thank you for spending time explaining!
Pingback: The name of birds, share 1 – TOP Show HN