Hi,
Be sure you have understood the preceding posts before reading this one.
For archives and even better archives, see the links below.
The Paradoxical combinators
I recall that a combinator X is a fixed point of a combinator Z if ZX =
X.
For example, all combinators (birds) are fixed point of the identity
combinator,
given that for any x Ix = x. Curiously enough in many forest all
combinators
have a fixed point.
The "paradoxical combinator", or "fixed point combinator" is a
combinator
which find that fixed point of any given combinators.
PROPOSITION 1: if a forest contains a bluebird B, where Bxyz = x(yz),
and a MockingBird M, that is Mx = xx, then ALL birds have indeed a
fixed point P.
Proof: All bird x have BxM(BxM) as a fixed point, that is BxM(BxM) is
always a fixed point of x, indeed:
BxM(BxM) = x(M(BxM)) = x(BxM(BxM)). OK?
PROPOSITION 2: If a forest contains a lark L, i.e. Lxy = x(yy), then
again ALL birds
will have a fixed point. Indeed all birds x have Lx(Lx) as a fixed
point:
Lx(Lx) = x(Lx(Lx)) (directly from the dynamic of L). OK?
Saying that all birds in a forest have a fixed point is not the same as
saying that there is,
in the forest a bird capable of finding that fixed point. Let us show
that if the forest
contains a starling and a lark, then there is such a bird (called a
paradoxical combinator,
or a fixed point combinator. raymond called them "wise bird", and I was
used to call them
"crazy bird" given that they can have some crazy behavior).
To find a fixed point combinator, it is enough, for example, to find a
bird which on x
will generate Lx(Lx).
But Lx(Lx) is just SLLx
And thus SLL is a fixed point combinator. SLLx = x(SLLx) given that
SLLx = Lx(Lx). OK?
(Of course SLL is an abbreviated name for combinator
S(S(S(KS)K)(KS(SKK)(SKK)))(S(S(KS)K)(KS(SKK)(SKK)))
given that we have shown L = SB(KM); and B = S(KS)K, and M = SI I=
S(SKK)(SKK)
cf solution 2 in COMBINATORS IV (see links below).
Obviously, a forest which contains S and K, like our current
"everything theory",
contains L (or a B and a M) and, thus, is such that all birds have a
fixed point.
Such a forest also contains fixed point combinators. Some day we will
justify
why any SK-forest contains really all possible birds.
WHAT'S the USE of PARADOXICAL combinators?
Well, you should be able to solve an exercise like finding a combinator
A such
that its dynamics is described by Axyz = y(yx)zz. Some other day we
will make this
precise by giving an *algorithm* for solving such problem (which
solutions exist
in all "sufficiently rich forest like the SK or BWCK forest). With the
fixed point combinators
you should be able to solve "recursive equations" like: find a A such
that its dynamics
is described recursively by Axyz = xxA(Ayy)z. How?
Just find a B such that Baxyz = xxa(ayy)z (A has been replaced by a
variable a).
This is a traditional (non recursive) exercise.
Then YB gives the solution of the recursive equation. (Y is the
traditional name for
a paradoxical combinator). Exercise: why?
EXERCISES:
Find an infinite eliminator E, that is a bird which eliminates all its
variables: Ex = E, Exy = E, etc.
Find an perpetual permutator, that is a bird which forever permutes its
two inputs: its dynamics is
as follow: Pxy =: Pyx =: Pxy =: Pyx etc. (I recall "=:" is the
reduction symbol of the dynamics; it
is the left to right reading of the "dynamics"). Etc.
I mean: solve the following equations (little letters like x, y z are
put for any combinator, A is put
for the precise combinator we are ask searching for):
Ax = A
Ax = xA
Axy = Ayx
Ax = AAx
A = AA
Ax = AA
Ax = x(Ax)
Obviously, Y is useful for the recursive programming. This will be
illustrate when when we will do
some logic and some arithmetic (soon on a screen near you).
After that you should be able to program any function with a
combinator. And after that we will
make a move enabling us to come back to our basic problems: where does
mind and matter
come from, ..., how to put a reasonable measure on the set of all
computations, ...
Archives and better archives:
COMBINATORS I is
http://www.escribe.com/science/theory/m5913.html, or better:
http://www.mail-archive.com/everything-list.domain.name.hidden/msg05920.html
COMBINATORS II is
http://www.escribe.com/science/theory/m5942.html, or better:
http://www.mail-archive.com/everything-list.domain.name.hidden/msg05949.html
COMBINATORS III is
http://www.escribe.com/science/theory/m5946.html, or better:
http://www.mail-archive.com/everything-list.domain.name.hidden/msg05953.html
COMBINATORS IV is
http://www.escribe.com/science/theory/m5947.html, or better:
http://www.mail-archive.com/everything-list.domain.name.hidden/msg05954.html
COMBINATORS V is
http://www.escribe.com/science/theory/m5948.html, or better:
http://www.mail-archive.com/everything-list.domain.name.hidden/msg05955.html
COMBINATORS VI
http://www.escribe.com/science/theory/m5950.html,
+
http://www.escribe.com/science/theory/m5951.html, or better, just:
http://www.mail-archive.com/everything-list.domain.name.hidden/msg05957.html
Summary:
abc abbreviates ((a b) c)
Kxy = x
Sxyz = xz(yz)
Combinators combine.
===========================
Bruno
http://iridia.ulb.ac.be/~marchal/
Received on Thu Mar 10 2005 - 10:37:49 PST