# 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 (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 left.in port named “1”, a right.in 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.]

# Chemlambda strings

I uploaded Chemlambda strings at Figshare.

“Chemlambda is an asynchronous graph rewrite automaton which uses a carefully selected family of graph rewrites of the kind encountered in Interaction Nets (IN). In this article is given a version of the graphs and rewrites which is more chemistry friendly. It is argued that real chemistry has enough place for accomodating chemlambda. The use of IN rewrite patterns in real chemistry, as templates of concrete chemical reactions, is an unexplored direction towards molecular computers. The simulations which validate chemlambda as a toy chemistry show that there is a big potential in this direction.”

The article is paired with the needs repository.  Look down the first page of the article for contact mail.

So what’s new with respect to chemlambda?

1. It is conservative. I said previously that it can be done, but here is the proof now.

2. It is open to vast generalization. I explained previously that there is not much lambda in chemlambda, as a proof see Turing machines, chemlambda style. Now it has the form (can be easily put into the form) of a permutation automaton. A permutation automaton is simply a program which takes as input a (maybe huge) permutation, probably with decorations on it (i.e. is a permutation of some big set, specified, not only a permutation of 1, …, N) and then it applies (randomly) pre-defined templates of permutations, whenever it detects a pattern into the permutation and moreover the random number generator produces an output of a certain difficulty 🙂

3. The paired needs repository contains already the main program. You can figure out how it functions, even if I have not added yet the functions libraries.

4. It is chemically friendly… Read the article.

Why chemlambda strings?

Because now we think about chemlambda molecules as being made by lists with sticky ends. These are the strings.

Each list (string) has two ends. So if there are N strings, then there are 2N nodes (ends of strings) and 3N edges. An edge is given by the fact that every list end appears in another list (interior).

Attention, it is not forbidden (actually happens, but not for graphs associated to lambda terms)  to also have loops. A loop is a list which you take and cut it’s start and end then you glue it back.

So if you take such a structure then you shall have a succ and pred functions, as well as a function gamma which taked a list end and gives you the list end place into another list.

For simplicity one can duplicate the nodes (so that now we have 4N nodes instead of 2N) and think about gamma as connecting the node which is an end of a list with the node which is an element of another (or the same) list.

Tell me if that rings a bell to you!