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/
Received on Fri Feb 04 2005 - 09:16:17 PST