Category Archives: chemlambda

Hapax chemlambda

Chemistry is a game with a pair of dices.

You roll two dices and act. The dices are permutohedra.

Which leads to ask what certain chemistries (artificial or real) have so special. The conjecture is that (probabilistically speaking) a sizeable proportion of them are special.

For example, we can evade the lambda calculus by choosing one of the  14400 rewrites for ( β with random right patterns) .

Hapax chemlambda!

Stick-and-ring graphs (I)

Until now the thread on small graph rewrite systems (last post here) was about rewrites on a family of graphs which I call “unoriented stick-and-ring graphs”. The page on small graph rewrite systems contains several formalisms, among them IC2, SH2 and system X are on unoriented stick-and-ring graphs and chemlambda strings is with oriented edges. Emergent algebras and Interaction Combinators are with oriented nodes. Pseudoknots are stick-and-ring graphs with oriented nodes and edges.

In this post I want to make clear what unoriented stick-and-ring graphs are, with the help of some drawings.

Practically an unoriented stick-and-ring graph is a graph with colored nodes, of valence 1, 2 or 3, which admit edges with the ends on the same node. We imagine that the nodes have 1, 2, or 3 ports and any edge between two nodes joins a port of one with a port of another one. Supplementary, we accept loops with no nodes and moreover any 3-valent node has a marked port.


If we split each 3-valent node into two half-nodes, one of them with the one marked port, the other with the remaing two ports, then we are left with a collection of disjoint connected graphs made of 1-valent or 2-valent nodes.


These graphs can be either sticks, i.e. they have 2 ends which are 1-valent nodes, or they can be rings, i.e. they are made entirely of 2-valent nodes.


It follows that we can recover our initial graph by gluing along  the sticks ends on other sticks or rings. We use dotted lines for gluing in the next figure.


A drawing of an unoriented stick-and-ring graph is an embedding of the graph in the plane. Only the combinatorial information matters. Here is another depiction of the same graph.marked-graphs-3



Fold rewrite, dynamic DNA material and visual DSD

As it happened with chemlambda programs, I decided it is shorter to take a look myself at possible physical realizations of chemlambda than to wait for others, uninterested or very interested really, people.

Let me recall a banner I used two years ago[Knitting-Crown]-Keep-Calm-And-Use-Rna-For-Interaction-Nets

It turns out that I know exactly how to do this. I contacted Andrew Phillips, in charge with Microsoft’ Visual DSD  with the message:

Dear Andrew,

I am interested in using Visual DSD to implement several graph-rewriting formalisms with strand graphs: Lafont Interaction Combinators, knots, spin braids and links rewrite systems, my chemlambda and emergent algebra formalisms.

AFAIK this has not been tried. Is this true? I suggest this in my project chemlambda but I don’t have the chemical expertise.

About me: geometer working with graph rewrite systems, homepage: or

Some links (thank you for a short reception of the message reply):

– github project:
– page with more links:
– arXiv version of my Molecular computers article

Emergent algebras:
– em-convex


I still wait for an answer, even if Microsoft’ Washington Microsoft Azure and Google Europe immediately loaded the pages I suggested in the mail.

Previously, I was noticed by somebody [if you want to be acknowledged then send me a message and I’ll update this] about Hamada and Luo Dynamic DNA material with emergent locomotion behavior powered by artificial metabolism  and I sent them the following message

Dear Professors Hamada and Luo,

I was notified about your excellent article Dynamic DNA material with emergent locomotion behavior powered by artificial metabolism, by colleagues familiar with my artificial chemistry chemlambda.

This message is to make you aware of it. I am a mathematician working with artificial chemistries and I look for ways to implement them in real chemistry. The shortest description of chemlambda is: an artificial chemistry where the chemical reactions are alike a Turing complete family of graph rewrites.

If such a way is possible then molecular computers would be not far away.

Here is a list of references about chemlambda:

– GitHub repository with the scripts
– page which collects most of the resources

Thank you for letting me know if this has any relation to your interests. For my part I would be very thrilled if so.

Best regards,
Marius Buliga

Again, seems that these biology/chemistry people have problems with replies to mathematicians, but all ths makes me more happy because soon I’ll probably release instructions about how everybody could make molecular computers along the lines of Molecular computers.

I’ll let you know if there are future “inspiration” work. Unrelated to chemlambda, there are several academic works which shamelessly borrow from my open work without acknowledgements, I’ll let you know about these and I’ll react in more formal ways. I hope though this will not be the case with chemlambda, however, this happened before twice at least.  (I say nothing about enzymes/catalysts, category theory and cryptocurrencies… for the moment.)

Finally, here is a realization of the lambda calculus beta rewrite via a FOLD rewrite


which shares a relation with the ZIP rewrite from Zipper Logic. It seems I was close to reality,  now though I got it exactly 🙂 .

Let’s talk soon!




Small graph rewrite systems (3)

Previous posts on the same subject are (1) (2). Related is this post.

In this post I update the small rewrite system SH-2.1 to SH-2.2.  If you look at SH-2.1, it has 3 rewrites: SH, GL and RM.

None of these rewrites allow two “sticks” to merge or one stick to transform into a ring.

Compare with the interaction combinators inspired IC-2.1, with the rewrites DIST, RW1 and RW2. Is true, that system is too reactive, but it has one rewrite, namely RW2, which allows two sticks to merge.

A rewrite which has this property (sticks merge) is essential for computational purposes. The most famous of such rewrites is the BETA rewrite in lambda calculus, or the \gamma \gamma and the \delta \delta rewrites from interaction combinators:


(figure from Lafont article).

In the oriented sticks and rings version of chemlambda we have the rewrites BETA (or A-L) and FI-FOE, with the same property.



We shall modify therefore one of the rewrites from SH-2.1.

The SH-2.2 system

We keep the rewrites SH and GL from the SH-2.1 system:




and we replace the rewrite RM with the new rewrite R2:


The new rewrite R2 needs a ring!

Let’s show that SH-2.2 is better than SH-2.1. All we need is to be able to do the rewrite RM from SH-2.1 in SH-2.2. Here is it.


Mind that the ring from the upper right graph is not the same as the ring from the bottom graph. Indeed, in the rewrite R2 the ring from the bottom is consumed and  a new ring appears from the merging of the ends of the stick with two blue nodes which sits on the top of the other stick with two yellow ends from the bottom graph.

Compared with the original RM rewrite


we have an extra ring at the left and at the right of the rewrite RM, as it appears in SH-2.2. Otherwise said the ring plays the role of an enzyme.






Data, channels, contracts, rewrites and coins

We can think about all these in terms of dimension.

Data are  like points, 0 dimensional.

Channels (of communication) are 1-dimensional. They are the fundamental bricks of IT. They are not enough, though.

Contracts are 2-dimensional. A contract is an algorithm over channels.

As an example, here’s how we can turn a graph rewrite system in the  sticks and rings version  into a contract-like one.

For the (oriented) sticks and rings version of chemlambda see this. Two small rewrite systems involving non-oriented sticks are described here  and there.

The closest algorithm relevant for this post is the one from needs.  I shall mention in ths post names from there, like  “succ”, “ccus”, “gamma” and “ammag”.

We can descrine a sticks and rings graph with two invertible functions. Each node of a trivalent graph is decomposed as two half-nodes. Indees, cut a trivalent node  in half, you get a half-node with one half-edge  (this is type  I half-node) and another half-node with two half-edges (this is type II half-node).   Each stick has two ends which are type I half-nodes and it is a list which starts and ends with type I half-nodes and contains  otherwise only type II hald-nodes. A ring is a circular list made of type II half-nodes.

Succ and it’s inverse ccus is the function (permutation) which for any half-node from a  stick or ring gives the sucessor half-node, if any (or the predecessor half-node  in the case of ccus).

Gamma and it’s inverse  ammag is the function (permutation) which pairs each type I half-node with it’s type  II other half-node.

The new thing here is that we shall think about half-nodes as names of channels in an asynchronous pi-calculus.

In the needs algorithm the rewrites (which are  conservative in the number of half-nodes) are small permutations of half-nodes. The gamma-ammag function is passive, in the sense that it never changes.   The rewrites are  random.

In the version I   propose here   each half-node is a unidirectional channel which can be used to communicate other channels names and some data. In the case of the graph rewrite systems we discuss here the other data is the color of the (half-)node.

In the case of chemlambda strings we  need a bit for the half-node type and 2 bits for the colors. As a (half) tongue-in-cheek I used DNA or RNA like encoding, like in this screen casting, to turn a mol file into the sticks and rings version.


In the version proposed here we  change the algorithm of random application of a rewrite with an algorithm which involves only communication via the channels  associated with the half-nodes.

Here is  the description of a SH rewrite


Each  stick is the property of somebody (A, B, C, D, …), say an actor. A stick is a list of  channels names.  So the data (0-dim) are the channels names, organized in lists which are managed by actors.

Actors can send messages through channels and also they can edit their list.

A rewrite, here the SH,  is an contract, i.e. an algorithm which describes how to achieve the rewrite via communication and editing of list, such that each actor can locally  execute it’s part.

But how can we  read  such a contract? In many ways, because the formalism is so general. For example: B and D exchange C in the place A, witnessed by the notary node e1.

Then what can be the pairs  yellow-blue and blue-blue? Recall that originally the SH rewrite is


Well, coins? Or coin (yellow-blue) and gas (blue-blue)?  Or receipts? Imagination is the limit and all can be made  in practice. If you are interested to make it real contact me.


Small graph rewrite systems (2)

I continue from the last post on small graph rewrite systems. Let’s see some more details about the SH-2.1 system.

The last post ends with a realization of the DIST rewrite in SH-2.1. We can do better than that, by showing that the DIST rewrite is reversible:




As you see, the two pairs yellow-blue and blue-blue play the role  of enzymes.

Another two interesting reactions are the following:


So the “yellow ends” duplicate, with a pair blue-blue as an enzyme.



The supplementary “blue ends” prune themselves, in a sort  of duality  with the “yellow ends”. This time there is a yellow-blue pair enzyme.


Small graph rewrite systems (I)

What happens if we use the sticks and rings description of  oriented fatgraphs, like in this post, but we drop the orientation? Moreover, what if we use as few colors as  possible and as few rewrites as possible?

For the sticks and rings version of chemlambda see this.

If we have oriented edges then the sticks and rings  image is equivalent with the usual oriented trivalent fatgraph. But if we drop the edges orientation something interesting happens. The trivalent nodes become invertible. Indeed, take for example, with the notations from chemlambda, a node as seen in a mol file:

A 1 2 3

It means that we have a node “A” (i.e. application)   with a port named “1”, a port named “2” and a out port named “3”. To get a more precise idea, think about “1” as a term “T_1”, about “2” as a term “T_2” and about “3” as the term “T_1 T_2”.

In the sticks and rings version there is an edge which connects “1” and “3”, which is perhaps part  of a stick (which has two ends) or a ring (which has none). “1” and “3” appear as marks on that stick (or ring) and the stick (or ring) has an orientation so that the successor of “1” is “3”.

Another stick, which ends with the mark “2” and the node “A”, is glued between the marks “1” and “2”.

For a node like

FO 1 2 3

(i.e. a fanout) the oriented stick passes from “1” to “3” but this time the second stick starts with the node “FO” and the mark “2”.

Now, if we drop the sticks orientations, it means that we can no longer discern between say “A 1 2 3” and “A 3 2 1”. As an expression which depends on the port “2”,  we can go from “1” to “3” as easily as we go from “3” to “1”, so it  looks invertible.

As a first try let’s see how does a non-oriented sticks and rings version of Lafont interaction combinators look like. We need only two colors, to discern between the \gamma and \delta combinators. We shall not use the combinators with only one port.

The IC-2.1 system

The \gamma \delta  rewrite will be like a DIST rewrite from chemlambda, only unoriented.



Then, the \gamma \gamma looks like this


and finally the \delta \delta may be seen like this


As you see all rewrites are made conservative in the number of nodes, by the addition of supplementary 2-nodes sticks, call them “pairs” from now.


Now we have some problems:

  • the RHS of the DIST rewrite contains the pattern from the LHS  if we add another pair yellow-blue. That is bad because it means we can continue indefinitely the same rewrite if we have enough yellow-blue pairs  at our  disposal
  • practically almost any sticks and rings graph is extremely reactive, because any combination of nodes colors which are neighbours on a stick or ring will trigger a rewrite. Question: which are the graphs which are fully reduced?
  • if we look back to Lafont interaction combinators, then we see that our system has more rewrites than the original. Indeed, that is because the non-oriented sticks and rings image is ambiguous, not equivalent with the interaction combinators. This explains the abundance of patterns for reduction.


The SH-2.1 system

Let’s try another rewrite system, non-oriented sticks and rings and two colors. We’ll take the shuffle trick rewrite as basic, this time:


Then we add a “glue” rewrite


and a “remove” rewrite



Now we are in the realm of emergent algebras, with the yellow node as a generic dilation and the blue node as a fanout (more about this later). We can do lots of funny things with this small system, for example we can do a DIST:





There is a remarkable behaviour here. Look at the pair blue-blue, you have it at the left of the “simulated” DIST and at the right of it.

The pair blue-blue behaves like an enzyme!

[Continues with this post.]