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:


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).


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.



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).



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.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s