Tag Archives: category theory

Blockchain categoricitis 2, or life as an investor and a category theory fan

… or the unreasonable effectiveness of category theory in blockchain investments.

A year ago I wrote the post Blockchain categoricitis and now I see my prediction happening.

Categoricitis is the name of a disease which infects the predisposed fans of category theory, those which are not armed with powerfull mathematical antibodies. Show them some diagrams from the height of your academic tower, tell them you have answers for real problems and they will believe.

Case in point: RChain. See Boom, bust and blockchain: RChain Cooperative’s cryptocurrency dreams dissolve into controversy.

Yes, just another cryptocurrency story… Wait a moment, this one is different, because it is backed by strong mathematical authority! You’ll practically see all the actors from the GeekWire story mentioned in the posts linked further.

Look:

Guestpost at John Baez blog: RChain (archived)

“Programmers, venture capitalists, blockchain enthusiasts, experts in software, finance, and mathematics: myriad perspectives from around the globe came to join in the dawn of a new internet. Let’s just say, it’s a lot to take in. This project is the real deal – the idea is revolutionary […]”

RChain is light years ahead of the industry. Why? It is upholding the principle of correct by construction with the depth and rigor of mathematics.”

__________

Another one, in the same place: Pyrofex (archived). This is not a bombastic guestpost, it’s authored by Baez.

Mike Stay is applying category theory to computation at a new startup called Pyrofex. And this startup has now entered a deal with RChain.”

Incidentally (but which fan reads everything?) in the same post Baez is candid about computation and category theory.

“When I first started, I thought the basic story would be obvious: people must be making up categories where the morphisms describe processes of computation.

But I soon learned I was wrong: […] the morphisms were equivalence classes of things going between data types—and this equivalence relation completely washed out the difference, between, say, a program that actually computes 237 × 419 and a program that just prints out 99303, which happens to be the answer to that problem.

In other words, the actual process of computation was not visible in the category-theoretic framework.” [boldfaced by me]

(then he goes on to say that 2-categories are needed in fact, etc.)

In Applied Category Theory at NIST (archived) we read:

“The workshop aims to bring together two distinct groups. First, category theorists interested in pursuing applications outside of the usual mathematical fields. Second, domain experts and research managers from industry, government, science and engineering who have in mind potential domain applications for categorical methods.”

and we see an animation from the post  “Correct-by-construction Casper | A Visualization for the Future of Blockchain Consensus“.

________________________

I never trusted these ideas. I had interactions with some of the actors in this story   (example) (another example), basically around distributed GLC . Between 2013-2015, instead of writing programs the fans of GLC  practically killed the distributed   GLC project  because it was all the time presented in misleading terms of agents and processes, despite my dislike. Which made me write chemlambda, so eventually that was good.

[hype] GLC and chemlambda are sort of ideal Lisp machines which you can cut in half and they still work. But you have to renounce at semantics for that, which makes this description very different from the actual Lisp machines.  [/hype]

 

 

Blockchain categoricitis

The following conditions predispose you to categoricitis and this can be very bad for your savings:

  • baby boomer
  • you were a programmer once or you made money from that
  • you are a known researcher but your last original idea was last century
  • interested in pop science
  • you think an explanation by words can be shorter than one by mathematics
  • don’t know mathematics at the researcher level
  • you think you’re smart
  • you are all about internet, decentralization and blockchains
  • you believe in ether or may have pet alternative theories about the universe
  • you are not averse to a slight cheating, if this is backed by solid institutions or people.

More of these conditions present, more are you at risk.

(If you work in the money business then you are immune. For you, those people with categoricitis are a golden opportunity.)

The most dangerous is when you feel the need to be blockchain cool, but you missed the Bitcoin train. Your categoricitis is then grabbing you, making you smell like money. You feel the need to invest. Hey, what’s the problem? Is backed by math, banks and M$.

You’ll be relieved rather sooner than later 🙂

Walker eating bits and a comment on the social side of research

This post has two parts: the first part presents an experiment and the second part is a comment on the social side of research today.

Part 1: walker eating bits.  In this post I introduced the walker, which has been also mentioned in the previous post.

I made several experiments with the walker, I shall start by describing the most recent one, and then I shall recall (i.e. links to posts and vids) the ones before.

I use the chemlambda gui which is available for download from here.

What I did: first I took the walker and made it walk on a trail which is generated on the fly by a pair A-FOE of nodes. I knew previously that such a pair A-FOE generates a trail of A and FO nodes, because this is the basic behaviour of the Y combinator in chemlambda. See the illustration of this (but in an older version, which uses only one type of fanout nodes, the FO) here.  Part of it was described in the pen-and-paper version in the ALIFE14 article with Louis Kauffman.

OK, if you want to see how the walker walks on the trail then you have to download first the gui and then use the gui with the file walker.mol.

Then I modified the experiment in order to feed the walker with a bit.

A bit is a pair of A-FO nodes, which has the property that it is a propagator. See here the illustration of this fact.

For this I had to modify the mol file, which I did. The new mol file is walker_eating_bit.mol .

The purpose of the experiment is to see what happens when the walker is fed with a bit. Will it preserve its shape and spill out a residue on the trail? Or will it change and degenerate to a molecule which is no longer able to walk?

The answer is shown in the following two screenshots. The first one presents the initial molecule described by the walker_eating_bit.mol.

walker_eating_bit_step0
At the extreme right you see the pair A-FOE which is generating the trail (A is the green big node with two smaller yellow ones and a small blue one and the FOE is the big yellow node with two smaller blue ones and a small yellow one). If you feel lost in the notation, then look a bit at the description in the visual tutorial.

In the middle you see the walker molecule. At the right there is the end of the trail. The walker walks from left to right, but because the trail is generated from right to left, this is seen as if the walker stays in place and the trail at its left gets longer and longer.

OK. Now, I added the bit, I said. The bit is that other pair of two green nodes, at the right of the figure, immediately at the left of the A-FOE pair from the extreme right.

The walker is going to eat this pair. What happens?

I spare you the details and I show you the result of 8 reduction steps in the next figure.

walker_eating_bit_step8

You see that the walker already passed over the bit, processed it and spat it as a pair A-FOE. Then the walker continued to walk some more steps, keeping its initial shape.

GREAT! The walker has a metabolism.

Previous experiments.  If you take the walker on the trail and you glue the ends of the trail then you get a walker tchoo-tchoo going on a circular trail. But wait, due to symmetries, this looks as a molecule which stays the same after each reduction step. Meaning this is a chemlambda quine. I called such a quine an ouroboros. In the post Quines in chemlambda you see such an ouroboros obtained from a walker which walk on a circular train track  made of only one pair.

I previously fed the walker with a node L and a termination node T, see this post for pen and paper description and this video for a more visual description, where the train track is made circular as described previously.

That’s it with the first part.

Part 2: the telling silence of the expert. The expert is no lamb in academia. He or she fiercely protect the small field of expertise where is king or queen. As you know if you read this open notebook, I have the habit of changing the research fields from time to time. This time, I entered into the the radar of artificial chemistry and graph rewriting systems, with an interest in computation. Naturally I tried to consult as many as possible experts in these fields. Here is the one and only contribution from the category theory church.  Yes, simply having a better theory does not trump racism and turf protection.  But fortunately not everything can be solved by good PR only. As it becomes more and more clear, the effect of promotion of mediocrity in academia, which was consistently followed  since the ’70, has devastating effects on the academia itself. Now we have become producers of standardised units of research, and the rest is just the monkey business about who’s on top. Gone is the the trust in science, gone are the funds, but hey, for some the establishment will still provide a good retirement.

The positive side of this big story, where I only offer concrete, punctual examples, is that the avalanche which was facilitated by the open science movement (due to the existence of the net) will change forever the academia in particular. Not into a perfect realm, because there are no such items in the real world catalogue. But the production of scientific research in the old ways of churches and you scratch my back and I’ll scratch yours is now exposed to more eyes than before and soon enough we shall witness a phenomenon similar to the one happened more than 100 years ago in art, where ossified academic art sunk into oblivion and an explosion of creativity ensued, simply because of the exposure of academic painting along with alternative (and, mixed with garbage, much more creative artists) works in the historical impressionist revolution.

______________________________________________

 

Some categorical thinking about chemlambda and why this may suck

I continue to file here, for dissemination and further processing, useful bits written about chemlambda and the Distributed  GLC model of decentralized computation.

Please contribute, contradict and dispute me here or by private communications, of course under the constraints of long attention span and reasonable understanding of the subject.

 

_________________________________

If you want a category for chemlambda, then is the category with arrows being the graph rewrites and with objects chemlambda graphs.

That is the sloppy formulation. Here is one more precise. But before, let’s be sure you know what a chemlambda graph is and what a move (or graph rewrite) is.

A chemlambda graph (aka a molecule) is any graph made by a finite number of the following graphical elements:

4_chem

The 3valent nodes are all locally planar. What is the meaning of this? Read the following comic strip (click on the image to make it bigger).

node_application_1

The list of moves (graph rewrites) of chemlambda is given in several places, for a short clear description read for example

M. Buliga, L.H. Kauffman, Chemlambda, universality and self-multiplication,    arXiv:1403.8046  , accepted in the
ALIFE 14: The Fourteenth International Conference on the Synthesis and Simulation of Living Systems, July 30th – Aug 2nd 2014, New York

Let’s take one move, the graphic beta move, how it functions? See the following image.

convention_2_mod

________________________________

OK then, what is a category theory approach to chemlambda?

… (and, more importantly, to  asynchronous decentralized computations with chemlambda?)

One possible formulation is the following.

1. You know that you can define a groupoid only in terms of arrows, as a family of items (arrows) with a partially defined composition operation which takes a pair of arrows from the domain of definition and gives an arrow, with a totally defined inverse operation which takes an arrow and gives its inverse.

There are some axioms satisfied by these two operations.
You identify the objects of the groupoid as arrows a^{-1} a.

2. Take then a graph in chemlambda (call it G) and associate to it the groupoid R(G) which is generated by all the graph rewrites which can be done on G. It is a groupoid, because all graph rewrites are reversible  (this gives the inverse) and because the composition of graph rewrites is the composition of arrows.

3. Remark that the objects of this groupoid are not simply the graphs which can be related to G by a finite sequence of reductions, but more. An object appears to be a graph with a selected subgraph which is the subject of the move.

4. There is more structure. Because each arrow is a graph rewrite, and each graph rewrite has a name, it follows that you have a decorated groupoid, with arrows decorated by a word in the free group generated by the graph
rewrites names.

5. You may want to privilege some directions of moves (move is a shorter name for graph rewrite) over the others. For example the beta move in the usual direction over the beta move in the opposite direction. But you may want to keep other directions as likely to be used, for example like in the
CO-COMM (co-commutativity move) and CO-ASSOC (co-associativity move).

 

convention_3

All in all this may give several variants of supplementary structures, all coming actually from supplementary structure over the free group generated by the moves names. Among them:
5.1. Partial order relations, like: an object A is smaller than an object  B if there is an arrow from A to B decorated only by positive or neutral moves.
5.2. Give to each move name a probability such that the probability for the move in the positive direction is greater than the probability for the  move in the opposite direction, and 50-50 for the neutral moves. Then define random walks on the groupoid.

6. Now, there is more structure, but it may be misleading. Add a lattice structure to the objects, coming from the fact that a disjoint union of two chemlambda graphs is a chemlambda graph. This will produce more objects than before, because until now the objects are a graph with one place selected for a rewrite. You get a bigger groupoid, which admits as objects chemlambda graphs with more than one place selected for rewrites and  new arrows which can be described as parallel composition of  other arrows.

From this point it matters very much what you choose to do.  Because it starts to suck, here is why.

At point 6 is  already introduced a global point of view, namely that there is any meaning to parallel composition (the problem is that in the real world there is no  meaning of this composition in the absence of a global point of view).

Another critic I have against such an approach is that the groupoid R(G) and most of the other structure introduced is global, in the sense that it is needed only for explaining the model by following the category fashion. As an outcome we obtain  a God’s view of the model.

You don’t need this  structure to define what a local move is.

Even worse, let’s  make an analogy between chemlambda graphs and you, me, any other user of the net or any living being in the world,  and between moves and any interactions between  you, me and anybody else.
Then you don’t need to know how, in China, that donkey stumbled upon that rock while we have a meaningful conversation. Heck, you can’t even define what means that as we have this conversation that donkey in China stumbled upon  that rock, unless you use some external, unneeded reference.

Even less sense makes to model this by  saying  that it does not matter because our conversation is the same in the case the donkey stumbled before you read this post or after you read this post.

 

Because such an explanation of a local, asynchronous interaction introduces by the back door that there is a global reference needed, but independent means the  succession relations with respect to this global reference do not matter.
_______________________________________________

 

 

A question and a comment about untyped lambda calculus

Question: Is there any formulation in terms of category theory of pure untyped lambda calculus, only with alpha-equivalence and beta-reduction, but not with eta-reduction? Please provide links to the relevant sources, which have to contain proofs.

My impression (which could be wrong) is that the answer is NO. It becomes YES with eta-reduction, am I right?

Comment: This is again about pure untyped lambda calculus, only with alpha-equivalence and beta-reduction. compared with my graphic lambda calculus.  So, in pure untyped lambda calculus there are only two moves: beta-reduction and (a collection of moves under the) alpha-equivalence. At first view, the graphic lambda calculus has much more moves. Let us neglect the emergent algebra moves, which are exterior to lambda calculus. Still, in graphic lambda calculus there are the  fan-out moves    and the pruning moves. Compare these moves with the long prose one has to write in order to really explain how alpha-equivalence works and how terms are written, with all rules and moves included so that a non-human computer might apply them.

UPDATE: The question, formulated as: “is lambda-beta representable?” is an open problem by Barendregt and others. See for the precise language the paper GRaph models of lambda-calculus at work, by C. Berline, Math Struct. for Comput. Sci. 16:1-37, 2006,  link to ps.