Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to create a K combinator in the enchanted forest? (To Mock a Mockingbird)

Recall that the K combinator is a constant function. It always returns its first argument:

Kxy = x for all y

In the book To Mock a Mockingbird the author presents an example of an enchanted forest containing talking birds. The birds have behavior:

Given any birds A and B, if you call out the name of B to A, then A will respond by calling out the name of some bird to you: this bird we will designate by AB.

Suppose the forest consists of three birds, A, B, and C. Is it possible for at least one of the birds to behave like the K combinator?

Below is a table that shows one possible set of behaviors for the birds in the enchanted forest. The first column has the name of each bird in the forest. The top row has the names that may be called out to each bird. The body is the response of a bird to a name. For example, if you call out the name of A to bird A, then bird A will respond with C (see row 2, column 2). Succinctly, AA = C. If you call out the name of B to bird A, then bird A will respond with B (see row 2, column 3). Succinctly, AB = B. What value should go into the empty slot for AC?

   | A    B    C
------------------
A  | C    B
B  | B    B    B
C  | A    A    A

Let’s see if we can make bird A behave like the K combinator. The above set of values look promising:

  • AA = C and Cy = A for all y. That is, (AA)y = A for all y.

  • AB = B and By = B for all y. That is, (AB)y = B for all y.

What value should be placed in the empty slot (AC)? Consider all the cases:

  • If AC = A then the value of Ay must be C for all y, which is clearly false. Therefore A cannot be the correct value for the empty slot.

  • If AC = B then the value of By must be C for all y, which is clearly false. Therefore B cannot be the correct value for the empty slot.

  • If AC = C then the value of Cy must be C for all y, which is clearly false. Therefore C cannot be the correct value for the empty slot.

Therefore no value can be placed in the empty slot to satisfy the condition (AC)y = C, for every y.

As far as I can tell, it is impossible to make any bird behave like a K combinator. I hope you will prove me wrong.

like image 887
Roger Costello Avatar asked May 31 '12 09:05

Roger Costello


2 Answers

I like Judge Mental's answer, so for those who are having problems getting it, I'll spell it out more.


Let G be the set of all functions.

Let F be a subset G such that |F| > 1 and ∀f ∈ F (f : F → F). (F is your set of birds.)

Let 1F be the identity function of F.

Suppose for a contradiction that there ∃k ∈ F (∀(f,g) ∈ (F×F) (kfg = f)). Fix such a k. In other words, ∀f ∈ F (kf is constant). By definition, ∀f ∈ F (kkf = k). So ∀f ∈ F (kf = 1F because k has a left inverse by Lemma below). Thus we have ∀f ∈ F (kf is constant and kf = 1F), which is clearly absurd because |F| > 1.

Lemma: Let (f,g) ∈ (F×F) such that kf = kg. By definition of k, ∀h ∈ F (kfh = f). So ∀h ∈ F (f = kfh = (kf)h = (kg)h = kgh = g). This can only happen if f = g. Thus k injective. Thus k must have a left inverse.

like image 101
Thomas Eding Avatar answered Nov 15 '22 16:11

Thomas Eding


You are correct. It is impossible for any finite number of birds greater than 1.

The simple argument is if there were such a bird K, every bird in the image of K would be constant (by definition), and every bird would be in the image of K (by a cardinality argument), including K itself, which is obviously non-constant.

like image 1
Judge Mental Avatar answered Nov 15 '22 17:11

Judge Mental