Hi,
Sorry for the delay.
We have seen how to program the blue bird B, the cardinal C and the Warbler W
with the kestrel K and the starling S. Could you define the starling S from
B, W and C?
It is not so simple. Now if we succeed, this will give us a second
equivalent theory.
I mean the sets:
{S K}
{W B C K}
generates by composition the same set of birds. Later we will see those
sets are maximal. They generate all the birds. It is two equiavlent
presentations of the same "everything theory". The first has two primitive
bird, the second has 4 primitives birds (because it can be shown you cannot
define W from B C K, nor B from W C K, etc.)
To show the sets {S K} and {W B C K} generate the same combinators (birds)
we must show how to define W, B, C and K from {S K}. But this has been done
(see previous post), for exemple W = SS(KI), B = S(KS)K and C = S(BBS)(KK).
So it remains to show inversely that S can be defined from W, B, and C (and
K except S does not eliminate any input and it is thus doubtless we need K).
I gave you the first line:
Sxyz = xz(yz)
= Cx(yz)z
Ah someone asks me why? Recall Cxyz= xzy, with x y z arbitrary
combinators, thus
Cx(yz)z = xz(yz) (the first argument of C was x, the second was (yz) and
the third was z).
Oops students are coming. I let you do the following more easy exercise:
Verify that S = B(BW)(BBC). That is verify that B(BW)(BBC)xyz = xz(yz).
This should be much easier.
Bruno
============================
COMBINATORS I is
http://www.escribe.com/science/theory/m5913.html
COMBINATORS II is
http://www.escribe.com/science/theory/m5942.html
COMBINATORS III is
http://www.escribe.com/science/theory/m5946.html
COMBINATORS IV is
http://www.escribe.com/science/theory/m5947.html
Resume:
Kxy = x
Sxyz = xz(yz)
===========================
http://iridia.ulb.ac.be/~marchal/
Received on Fri Feb 18 2005 - 09:24:49 PST