This is the same post: COMBINATORS VI
I'm just searching a way to format it so that it is
more readable in the archive.
----------------------------------------------------------------------------
I will provide a detailed solution of the last problem
for those who have perhaps missed the beginning.
Verify that S = B(BW)(BBC). That is
verify that B(BW)(BBC)xyz = xz(yz)
This should be much easier.
One awful solution would be, reminding that
B = S(KS)K, and that W = SS(KI)
and that C = S(BBS)(KK), that is
S((S(KS)K)(S(KS)K)S)(KK), to substitute
those the occurence of B, W and C by they
SK-programs, giving:
S = B(BW)(BBC) =
S(KS)K((S(KS)K)SS(K(SKK)))((S(KS)K)(S(KS)K)(S((S(KS)K)(S(KS)K)S)(KK)))
... and then applying that expression on xyz.
Obviously we have not programmed the elementary
compositor B, the elementary permutator C and the
elementary duplicator W for not using them. Yet this
gave an interesting definition of S in term of itself and
this rises the question if there is not some general
recursion phenomenon there and indeed there will be
a very general such phenomenon captured by a
combinator which is neither an eliminator, nor a
permutator, nor a duplicator, nor even an identificator
(like Ix = x) and which was called the paradoxical
combinators by Curry and Feys and is known today
as the fixed point combinator but that's for later.
So I recall:
Bxyz = x(yz)
Wxy = xyy
Cxyz = xzy
And 'course:
Kxy = x
Sxyz = xz(yz)
And let us verify that S = B(BW)(BBC)
I recall "=" means "act similarly"; thus we must
show that:
B(BW)(BBC)xyz = Sxyz = xz(yz)
Well Bxyz = x(yz) and please remember that
Bxyz abbreviates (((B x) y) z) and in particular
B(BW)(BBC)x abbreviates (((B (BW)) (BBC)) x)
and that that matches!
Another practical way (more practical than
by adding the left parenthesis!) is to fully
abbreviate the expression (like I do usually) and
remember that B (here) is trigged by its dynamic
when presented with three arguments and that
argument are *arbitrary* combinators:
so the expression B(BW)(BBC)xyz is
B (BW) (BBC) x y z
1 2 3
and you can write the dynamic of B by B123 = 1(23), meaning
that 1 denotes its first argument (BW), 2 its second (BBC) and
3 denotes x, so that
B(BW)(BBC)x gives (BW)((BBC)x) that is (fully abbreviated)
BW(BBCx). We must yet apply it to y and then z:
BW(BBCx)y
Oh! here we have a choice! Indeed
the B-dynamic match the first occurrence
of B and the second one. A famous result,
known as Church Rosser Theorem tells
us that as far as thereduction will converge
on some stable molecule, the path, and
thus those choice does not matter: we will
get the same stable molecule. Soon or
later we will come back on this, but let us
just choose the leftmost reduction (another
theorem will make some advertising for that
strategy, but things will appear to be non
trivial though ...). So we apply the B-rule
on leftmost B in: B W (BBCx) y giving
W((BBCx)y) that is (fully abbrev.)
W(BBCxy), and now we have also a
choice: either we apply W(BBCxy)
directly on z, or we reduce it further.
You could verify those alternate path
as exercise; let us apply W(BBCxy)
directly on z. This gives W(BBCxy)z
(and Wab = abb) thus W(BBCxy)z gives
(BBCxy)zz = (fully abbrev.) BBCxyzz,
and this gives by the B-rule B123 = 1(23),
(where 1, the first argument of B
is B itself, and 2 is C and 3 is x)
B(Cx)yzz which by the B
rule again (with 1 = (Cx), 2 = y, 3 = z)
gives (Cx)(yz)z, which by the C-rule C123= 132
(with 1 = x, 2 = (yz) 3 = z gives xz(yz). That's Sxyz
and so we have shown that
B(BW)(BBC) behaves like S.
To sum up: S = B(BW)(BBC) because
B(BW)(BBC)xyz
= BW(BBCx)yz
= W(BBCxy)z
= (BBCxy)zz
= B(Cx)yzz
= Cx(yz)z
= xz(yz) which what Sxyz gives.
Of course the original exercise I gave was harder: program
S from B, W and C. It consisted in finding that B(BW)(BBC) or
something similar. But how could we have found such expression?
A nice thing is that the verification above, which just use the
dynamics of B, C and W gives us the answer: just copy the
execution above in the reverse order (cf programming here is
inverse execution). I do it and I comment:
?xyz = < B, C, ...>xyz = xz(yz)
xz(yz) so this is what we want as the
result of B C W application
on xyz. So we must transform
xz(yz) as <B,C ..>xyz, that is
get those final "x)y)z)", or
xyz in fully abb. form.
Cx(yz)z what a clever move! we are
at once close to xyz, except
that we have two parentheses
too much, and one z to much.
To suppress one z we will
isolate it by moving the right
parenthesis to the left. That's
the inversion of the B-rule, so
we arrive at:
B(Cx)yzz and applying again the
B-rule, we get
(BBCxy)zz I let some left parenthesis
so that the W-rule
applicability is highlightened
W(BBCxy)z And now there just
remains a right parenthesis
we would like to push on the
left, which we can do by
two successive inverse B rule:
The first gives (with 1 = W, 2
= (BBCx) and 3 = y:
BW(BBCx)yz the second gives
with 1 = (BW), 2 = (BBC)
and 3 = x:
B(BW)(BBC)xyz we got what we wanted:
S = B(BW)(BBC). Both gives xz(yz) when
given x y and z (in that order!).
Question: is there a systematic method such
that giving any behavior like
Xxyztuv = x(yx)(uvut) <or what you want)
can generate systematically a corresponding
SK or BWCK -combinator?
The answer is yes. I let you meditate the question.
(This point will be made clear when we will meet
the terrible little cousins of the combinators
which are the *lambda expression*, (and which
in our context will just abbreviate complex
combinators), but I propose to progress
and make sure that the
SK combinator are Turing Universal.
I am not yet decided when I really should
introduce you to the paradoxical combinators,
which are rather crazy. Smullyan call
them wise birds, but I guess
it is an euphemism!
Mmhhh... Showing turing-universality
through the use of some paradoxical
combinator is easy (once we have defined
the numbers), but there is a risk you take
bad habits! Actually we don't need the
paradoxical combinators to prove the turing
universality of the SK forest, mmmmh...
Well actually I will be rather buzy so I give
you the definition of a paradoxical combinator
and I let you search one.
First show that for any combinator A there
is a combinator B such that AB = B.
B is called a fixed point of A. (like the center
of a wheel C is a fixed point of the rotations of
the wheel: RC = C). It is a bit amazing that
all combinators have a fixed point and that is
what I propose you try to show. Here are hints for
different arguments. 1) Show how to find a fixed
point of A (Arbitrary combinator) using just B, M
and A. (Mx = xx I recall). 2) The same using just the
Lark L (Lxy = x(yy) I recall).
Now, a paradoxical combinator Y is just a
combinator which applied on that A will give the
fixed point of A; that is YA will give a B such that
AB = B, that is A(YA) gives YA, or more generally
Y is a combinator satisfying Yx = x(Yx).
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
COMBINATORS V is
http://www.escribe.com/science/theory/m5948.html
Resume:
Kxy = x
Sxyz = xz(yz)
http://iridia.ulb.ac.be/~marchal/
Received on Mon Feb 21 2005 - 09:52:17 PST