# COMBINATORS II (solution of exercises)

`COMBINATORS I  was`

`http://www.escribe.com/science/theory/m5913.html`

`I recall all you need to know:`

```Kxy = x
Sxyz = xz(yz)```

```That's all!    (Well you are supposed to remember also that
abc is an abbreviation of ((ab)c), and a(bc) is an abbreviation for (a(bc)).```

I recall the exercices taken from "My First Everything Theory" Primary school Year 2127 :)
Solution are below.
Evaluate:

```(SS)KKK =
KKK(SS) = ?
(KK)(KK)(KK) = ?
(KKK)(KKK)(KKK) = ?```

`Evaluate:`

```K
KK
KKK
KKKK
KKKKK
KKKKKK
KKKKKKK
KKKKKKKK
KKKKKKKKK
KKKKKKKKKK```

A little more advanced exercices: is there a molecule, let us called it I, having
the following dynamic: (X refers to any molecule).

`IX = X    I = ?`

(Note I will use in this context the words molecules, birds, combinators, programs
as synonymous).
================================
SOLUTIONS:

```(SS)KKK = SK(KK)K = KK(KKK) = K
KKK(SS) = K(SS)
(KK)(KK)(KK) = KK(KK)(KK) = K(KK)
(KKK)(KKK)(KKK) = KKK = K```

```Note that the passage (KK)(KK)(KK) = KK(KK)(KK) comes just
from a use of the parentheses abbreviation rule which help to see
the match with the dynamic of K : Kxy = x, and indeed KK(KK),
when occuring at a beginning, matches Kxy with x = K  and y = (KK) = KK.```

```K    =  K
KK    =  KK
KKK    =  K
KKKK   =  KK
KKKKK    =  K
KKKKKK   =  KK
KKKKKKK    =  K
KKKKKKKK   =  KK
KKKKKKKKK    =  K
KKKKKKKKKK   =  KK```

```ok? (this was easy! if you have not succeed it means you
are imagining difficulties).
The next exercise is slightly less easy,
we are to program some identity operatort.```

`Ix = x    I = ?`

```We must find a program (that is a combinator, that is a
combination of K and S) which applied on any X gives that X.
We want for example that```

```I(KK) = (KK)
I(SSS) = SSS etc.```

```So we want that for all x   Ix = x.
But only Kxy is able to give x
so x = Kx? and we want Kx? matching the rule for S (we have only this one),
it is easy because whatever ? represents, Kx? gives x. So we can take
? = (K x) or (S x) or etc.
This gives x = Kx(Kx)   (or x = Kx(Sx) )
so that the rule S can be applied so that```

`x = Kx(Kx) = SKKx     (or x = Kx(Sx) = SKS)`

`Thus SKKx = x, and so a solution is`

`             I = SKK`

```It is our first program!
Another one is I = SKS (actually SK<anything stable> would work).```

`Let us verify. i.e. let us test SKK and SKS on KK:`

```  SKK(KK) = K(KK)(K(KK)) = KK
SKS(KK) = K(KK)(S(KK)) = KK```

```more general verification:
SKKx = Kx(Kx) = x```

`Any problem?  You see that programming is really inverse-executing.`

```===============================
New programming exercises:```

`Find combinators M, B, W, L, T such that`

`Mx = xx   (Hint: use your "subroutine" I, as a "macro" for SKK)`

`Bxyz = x(yz)`

`Wxy = xyy`

`Lxy = x(yy)`

`Txy = yx`

`Bruno`

`http://iridia.ulb.ac.be/~marchal/`

```

```