Well, COMBINATORS VI is a little bit more readable,
but I don't understand why it puts a blank line each line,
and, worst why it cuts the end of the posts. So
I resend the cutted line. Apology for your mail box.
COMBINATORS VI (sequel):
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:58:10 PST