COMBINATORS III

```COMBINATORS I was
http://www.escribe.com/science/theory/m5913.html
COMBINATORS II was
http://www.escribe.com/science/theory/m5942.html```

`Resume:`

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

That's all. (You are supposed to remember also that
abc is an abbreviation of ((ab)c), and a(bc) is an abbreviation for (a(bc)), so
Kxy is put for ((K x) y), and Sxyz is put for (((S x) y) z), and xz(yz) is put for
((x z)(y z)). We just don't write the left parentheses).

```I recall the last exercises:
Find combinators M, B, W, L, T and C such that
Mx = xx (Hint: use your "subroutine" I, as a "macro" for SKK)
Bxyz = x(yz)
Wxy = xyy
Lxy = x(yy)
Txy = yx
Cxyz = xzy  (I add this one)```

```I solve the two firsts one: M and B:
I recall we have already program the identity combinator I,
which is such that Ix = x for any combinators x. it is I = SKK, and
we can use it as a "subroutine".```

`1) We want find a combinator M such that Mx = xx.`

```We reason again by inverse-execution. We must transform xx in a
way such that it matches the right part of the dynamic of K or S. The
simplest way is by using I. Indeed xx = Ix(Ix), and this match the S rule.```

```Thus Mx = Ix(Ix)
= SIIx```

`and thus M = SII= S(SKK)(SKK).`

`2) We want to find a combinator B such that Bxyz = x(yz)`

```We need to find an expression equal (by the dynamic rule) to something
matching the right part of the S dynamic. We can use I, M or K and S.
Here K and S will be enough. Indeed```

```Bxyz = x(yz)
= (Kxz)(yz)     because x = Kxz
= S(Kx)yz       verify with all the parentheses if you don't see it.
= KSx(Kx)yz    because S = (KSx)
= S(KS)Kxyz```

`Thus B = S(KS)K     All right?`

```Note to understand what will follow it is not really necessary to develop
skills in the art of finding those programs, but you should be able to verify
them if you want to have the needed passive knowledge. Let us verify B on
any x y z:```

`Bxyz = S(KS)Kxyz = KSx(Kx)yz = S(Kx)yz = Kxz(yz) =x(yz).  OK?`

```Nevertheless I give you time (for the fun) to try to find W, L, T and C.
Could you find a combinator called INFINITY which is perpetually unstable?
That is INFINITY gives INFINITY, which gives INFINITY etc. (by the K S
dynamical rule).```

`To sum up our work:`

```I = SKK
M = SII = S(SKK)(SKK)
B = S(KS)K```

```Try to find W, with Wxy = xyy, L, with Lxy = x(yy), T with Txy = yx,
C with Cxyz = xzy, and INFINITY, with INFINITY dynamically transform
into INFINITY itself.  No question? Soon (that is after we solve the last
problems) we will have enough to make precise some nuances
`Bruno`
`http://iridia.ulb.ac.be/~marchal/`
```