COMBINATORS III

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Tue, 08 Feb 2005 12:51:54 +0100

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
between "mind" and "matter". Already!

Bruno

http://iridia.ulb.ac.be/~marchal/
Received on Tue Feb 08 2005 - 06:52:28 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:10 PST