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
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?
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:
<x-tad-bigger>COMBINATORS I is
http://www.escribe.com/science/theory/m5913.html, or better:
COMBINATORS II is
http://www.escribe.com/science/theory/m5942.html, or better:
COMBINATORS III is
http://www.escribe.com/science/theory/m5946.html, or better:
COMBINATORS IV is
http://www.escribe.com/science/theory/m5947.html, or better:
COMBINATORS V is
http://www.escribe.com/science/theory/m5948.html, or better:
+ http://www.escribe.com/science/theory/m5951.html, or better, just:
abc abbreviates ((a b) c)
Kxy = x
Sxyz = xz(yz)