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(<x-tad-bigger>S(S(KS)K)(KS(SKK)(SKK))</x-tad-bigger>)(<x-tad-bigger>S(S(KS)K)(KS(SKK)(SKK))</x-tad-bigger>)

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:*

<x-tad-bigger>COMBINATORS I is

http://www.escribe.com/science/theory/m5913.html, or better:

http://www.mail-archive.com/everything-list@eskimo.com/msg05920.html

COMBINATORS II is

http://www.escribe.com/science/theory/m5942.html, or better:

http://www.mail-archive.com/everything-list@eskimo.com/msg05949.html

COMBINATORS III is

http://www.escribe.com/science/theory/m5946.html, or better:

http://www.mail-archive.com/everything-list@eskimo.com/msg05953.html

COMBINATORS IV is

http://www.escribe.com/science/theory/m5947.html, or better:

http://www.mail-archive.com/everything-list@eskimo.com/msg05954.html

COMBINATORS V is

http://www.escribe.com/science/theory/m5948.html, or better:

http://www.mail-archive.com/everything-list@eskimo.com/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@eskimo.com/msg05957.html

Summary:

abc abbreviates ((a b) c)

Kxy = x

Sxyz = xz(yz)

Combinators combine.

===========================</x-tad-bigger>

Bruno

http://iridia.ulb.ac.be/~marchal/