Wednesday, April 30, 2014

'Z' is for the ζ-calculus

'Z' is for ζ-calculus  (pronounced 'zeta-calculus')

So, 'Z' is the last letter of the alphabet, unless you're Greek, then ζ is the sixth letter. The last letter of the Greek alphabet is Ω.

But we already did Ωm-Ωm-Ωm. Ram-Ram-Sita-Ram-Sita-Ram-Ram, so we're good there.

As α denotes the beginning of things, Ω (which on a Mac, you get by selecting option-Z. Fitting, that) denotes the end of things. That's why everybody back then got it when Jesus said: "I am the α and the Ω."

He was the package deal.

But look at you all, doing your A-to-Z challenge faithfully. Did you survive? Are you shell-shocked?

To put this into perspective, my mom was a journalist for local news for our local newspaper. She did the A-to-Z challenge, every day (except Sundays), every month, year-after-year.

So you've completed your A-to-Z challenge. Congratulations! Now, lather, rinse, repeat, every month, for the rest of your life, right?

And you thought one month was hard?

Okay, last entry for my A-to-Z guide book for surveyists, explorers and tourists of mathematics.

Okay, so the lambda calculus is the commingling of the κ-calculus (the contextual calculus) and the ζ-calculus (the control calculus), which we talk about in this post (disclaimer/citation: I get most of my information on the ζ-calculus from Hasegawa's seminal 1995 paper on the κζ-calculi). A good deal of attention, when it has been given at all, has been focused principally on the κ-calculus...

'And why not!' says most. In the κ-calculus you get things done. There's no application, but through composition of (first-order) functions and first-order tuple-types you have numbers, counting, addition, and all the rest come out of that.

With the control calculus you make functions that take functions as arguments.

τ : 1 | ((—) ↠ (—))

So reduction (to your answer) is of the form of the continuation-passing form, for a function in the ζ-calculus f : a → b is of the ζ-term form of:

ζ f : a → (c ↠ b)

Which is to say, the zeta-term, f, take a functionally-typed argument, a, and returns the continuation (c ↠ b).

Now, we got the κ-calculus to work by lifting function arguments to tupled-typed terms, and we saw that with the implementation of addition (here). Now, instead of lifting unit types to tuples, in the ζ-calculus we pass a function on x to the zeta-term by using functional composition, i.e.:

pass(c) o (ζ x . f) ~> f[c/x]

To be able to construct a function in the ζ-calculus we have the function-constructor, code:

given f : c → d and x is the 'constifying function' : 1 → c
we have f o x : 1 → d

from that we have code:

code(f) ζ x . (f o x) : 1 → (c ↠ d)

Boom! code, then, is a function that creates a function from nothing (the '1' type).

But, okay, what can you do with the ζ-calculus?

Well, since we don't have unit cartesian types, like we have in the κ-calculus, then the answer to that is, well, ... nothing, really.

I mean, it's possible to have function represent unit types then start composing them to build an algebra, but this approach is rather unwieldy. The ζ-calculus exists to show that the λ-calculus is perfectly decomposable into the κ-calculus and the ζ-calculus, and so control is usually mapped out in the ζ-calculus (although some directed flow is possible in the κ-calculus, itself alone, as we've seen) (link).

For example, to create the numbers zero and one are possible in the ζ-calculus, but when we try to represent two (that is, functionally, double application), we get this:

x : 1 → c
z : 1 → (c ↠ c)  pass(x) : (c ↠ c) → c
pass(x) o z : 1 → c  -- so we've got our constant continuation (step 1)
pass(pass(x) o z) : c ↠ (c → c) -- now we've got a continuation-creator
pass(pass(x) o z) o z) : 1 → c
ζx (pass (pass(x) o z) o z) : 1 → (c ↠ c) -- continuation-creator for the right-hand side
dupl ζz . ζx (pass (pass(x) o z) o z))) : 1 → ((c ↠ c) ↠ (c ↠ c))

And there we have it, the dupl(icate) function, or the number two, in the ζ-calculus.

Ugh!

Well, you did say you wanted to see it. I did, too. It's a morbid fascination of mine, watching this train wreck transpire.

The Takeaway here

But that's a reveal. Math isn't necessarily easy (shocker!) nor is it necessarily neat. Here we see in the ζ-calculus that it's difficult to express things (like, for example, the number two, or any unit types).

So, if you've got a correspondence (a provable one), all you have to do is to change categories to one where you can express what you need to simply and cleanly.

The application works here, and now, too.

I'm doing things slow and stupid, because I'm doing them the way I've always done them, the way I see how they're done.

Change categories. Somebody is doing what I'm doing, but doing it well. Somebody isn't doing what I'm doing, because they've moved onto better things — more sublime problems — ... I can do the same thing. All I have to do is change my perspective, how I see things, and then, seeing them anew, I can do what I need to do, what I want to do, simply and cleanly, then translate back down to the way I always do things, ...

Or hey, just move on, after having moved up.

It's called a 'lifting function.' It lifts an object from one category to another one, and in being lifted, the object is changed, and what it can do (its morphisms) are changed. And you can change it back 'down' (the co-ajoint function) or you can stay in the newly-lifted category, or you can lift again.

Math is neat that way, once you see that as a possibility.

Life can be like that, too.

Life is neat that way, once you see that as a possibility.

'Z' is for the ζ-calculus.

And with 'Z' we're all done doing our A-to-Z petit survey of mathematics and logic. I hope you had fun, for I had a blast writing these posts.

Thank you for reading them.