Friday, April 11, 2014
'J' is for the noble basis
'J' is for the noble combinator basis, JI
... and I've got to stop falling asleep mid-stream-of-consciousness/brain-dump (not 'bran'-dump! as that's something else entirely: 'brain'-dump!)
I'm going to entitle this article JILL after a lovely lady I knew, Ernimagilda Mucciaroni. 'Ernimagilda,' it turns out, is a nickname for Maria Theresa.
Santa Theresa, pray for us.
So, all combinators, and, by extension, a set of functional logics can be expressed by two combinators, the S:
S = \ x y z -> xz(yz)
and the K
K = \ x y -> x
combinators. Given those two combinators, and only those two combinators, you can rewrite any of the other combinators, like, for example, the I combinator:
I = \ x -> x
Or the B combinator:
B = \ x y z -> x(yz)
is simply SI, which I being defined above is S(SKK), or SII, I'll look that up. xxx
Great, we've got it all.
Problem. The K combinator, the constifier, drops a combinator from the discussion. So, if we're proving something, and we come across an inconvenient true, we simply apply the K combinator, and just drop it.
What if that instance of truth, that we just dropped, was the only instance in out universe of discourse?
Well, you could apply the continuation function and, going back in time, get it back. Or, without the continuation function, you could simply invent another universe, or reconstruct the one you were working with that truth back in there, and you're good to go, you can carry on from there.
Some philosophers have a problem with this, understandably, the 'oh, you can just go back and redo if you get it wrong the first time or if you find you needed it later'-excuse smacks of sloppiness, and in mathematics you have to be rigorous; you can't be sloppy. Imagine, for example, if they were blasé in constructing the Hilbert spaces? How much buy-in would there be if the disclaimer were added: "Oh, if something goes awry, just start over from the beginning and hope for the best. That should work"?
So, some site the dropping operator as the foundational problem, if there exists a truth in your space, why would you want to drop it? You'll only have to reconstruct it later on, anyway.
So, from that concern there arose the discussion around the 'noble' basis, or, how can we do what we need to do without discarding things that appear inconvenient or seem expedient to do so. After all, the Hilbert space is ... pretty big. There is room in this mathematics to carry around truths, regardless of their current utility. So, what combinators are necessary but also not destructive? Can this even be done.
It could. Four combinators showed to be of high utility in that they could construct the other combinators, except K, and they were S, M, B, and I or S, M, C, and I, depending on the preference of the proponent. Either set worked tolerably well.
But four combinators? Couldn't there be a reduced set that allowed one to use the noble set? After all, the SK-basis was originally the SKI-basis until someone brilliant realized that simply using S's and K's the I could be independently reproduced and therefore was unnecessary to form that basis.
It turns out in the noble SCMI-basis (or also in the SBMI-basis), there was. The J. The J combinator is defined as follows:
J = \ x y z w -> xy(xwz) xxx
The J in combination with another combinator would be able to reproduce the S (obviously), the C or the B (both, actually) and the M. Do you see which combinator?
Well, the T combinator:
T = \ x y -> yx
JII = \ I I z w -> II(Iwz) -I-> wx = T -- simplest realization
The R combinator:
R = \ x y z -> yzx
is JT or J(JII):
JT = \ T y z w -subst-> Ty(Twz) -T-> (Twz)y -T-> (zw)y = R
So, C from J, T, and R:
C = \ x y z -> xzy
RRR ... HA!
because RRRabc = RaRbc = Rbac = acb !
I = I -- simplest, simplest realization
M = \ x -> xx
But to get M, B would really help, so B is:
B = \ x y z -> x(yz)
B = C(JIC)(JI)xyz = (JIC)x(JI)yz = JICx(JI)yz = IC(I(JI)x)yz = C((JI)x)yz = JIxzy = Ix(Iyz) = B
So, M from J, I, B, C, R, T:
J(Ra)III = (Ra)I((Ra)II) = I((Ra)IIa = IIaa = aa = M, which, in combinators is:
RI(RI(RI(BJR))) ... RI moves the desired system down the chain ... for the 'J' anyway.
which is RI(RI(BJR))aI = RI(BJR)aII = BJRaIII = J(Ra)III
So, now S:
S = \ x y z = xy(xz)
So, the strategy here is to move the 'W' to before the x and then 'I' it out, or:
JabcI ... no because that gets us:
ab(aIc) and that is NOT what we want. we want: