The names of birds, part 2

Reader Joel" had an insightful comment on the first part of this series which I thought deserved a short episode of its own. Recall that we proved the theorem if a compositional forest contains a mockingbird then every bird in the forest has a fixpoint. An equivalent way to state that theorem is: if a forest contains a bird without a fixpoint then either the forest is not compositional or it contains no mockingbird. Joel's question was whether there is a more intuitive" way to understand why the mockingbird is so interesting that the presence of a bird without a fixpoint should prevent a mockingbird from existing in the same (compositional) forest.

The short version is: we'll say that two birds agree on an input if their outputs are the same for that input. The mockingbird is a bird that agrees with every other bird on at least one input. A bird without a fixpoint is a bird that can always produce a different output than its input. Their composition is a bird which disagrees with every bird in the forest on one input and therefore is not in the forest at all.

The long version is:

I find it easiest to get an intuition for a general rule by looking at some simple examples.

The first thing I'd note is that it is quite easy to construct a non-compositional forest containing a bird without a fixpoint. A simple example would be a non-compositional forest containing exactly two birds, A and M. Define them such that:

AA = M
AM = A
MA = M
MM = M

Plainly these are two different birds, since their responses disagree on input M. Plainly M is a mockingbird, since Mx=xx for all x in the forest. And plainly A has no fixpoint. This forest is not compositional because there is no bird C in the forest such that Cx=A(Mx) for all x. With such a small number of birds in the forest it seems quite reasonable that one might have no fixpoint.

Let's look at a more interesting example, this one in a compositional forest. Let's suppose there is a countable infinity of birds in the forest. By countable infinity" I mean that we can number each bird with a natural number; we've got bird 0, bird 1, bird 2, and so on. In fact, let's just use natural numbers as the names of the birds in this forest.

Since each bird needs a response to hearing the name of every other bird in the forest, we can imagine an infinite lookup table that says what each bird responds when it hears the name of another bird in the forest. We'll put the called to" bird on the vertical axis and the name called" on the horizontal axis:

 0 1 2 3 ... ------------ 0 | 9 5 2 5 ... 1 | 8 3 6 7 ... 2 | 0 1 2 3 ... 3 | 3 1 4 1 ...... | S | 1 2 3 4 ...... |

So in our notation 0 1=5, 2 3=3, and so on.

Let's suppose this forest is compositional and contains a bird, call it S, which has no fixpoint. We could choose any such S, but without loss of generality we shall pick a specific S, the bird where S 0=1, S 1=2, S 2=3, S 3=4, ... and so on; the successor" bird. Of course S has some number" name but we don't really care what it is, so we'll just alias" that one as S.

Now let's suppose there's a mockingbird in the forest and deduce a contradiction. The mockingbird tells us what is on the highlighted diagonal! That is, M 0=9, M 1=3, M 2=2, M 3=1, and so on. (As with S, M is an alias for some number" name but we don't know or care what it is.)

Now comes the fun bit. The forest is compositional, so therefore there exists a bird C such that Cx=S(Mx) for all x. We do care what the number name of C is. So, which is it?

C 0=10, and therefore C is not 0, because 0 0=9. But similarly, C 1=4, so C is not 1. And similarly C is not 2, 3, 4, 5, ... because C definitely disagrees with each of those functions I mean birds at the diagonal. But if C has no number name, then it is not in the forest at all, contradicting the statement that the forest is compositional. We now have deduced a contradiction, and therefore our assumption that M is in the forest is shown to be false.

By looking at a specific example - a countable forest with a successor bird - perhaps you have a better intuition about why Mx=xx and any bird S that has no fixpoint cannot coexist in a compositional forest: if they did then the bird C such that Cx=S(Mx) definitely disagrees with every bird in the forest on at least one input, and therefore the forest would not be closed under composition; there would always be a missing bird.

Next time on FAIC: We'll look at some more fun examples and then get back to compilation.