# Topology does not compute vs topology computes (I)

The article Zipper logic   arXiv:1405.6095  contains in its last section a discussion about the role of topology in computing formalisms which use topological objects, like tangle diagrams, or other graphs, and graph rewrites.

The purpose of this post is to start a discussion about the differences between two uses of graph rewrites in such formalisms.

I shall use further the NTC vs TC denomination suggested by Louis Kauffman instead of the longer one:

• NTC = “topology does not compute” , meaning that the graph rewrites are NOT part of the computation notion
• TC = “topology computes”, meaning that the graph rewrites are the fundamental blocks of the computation notion.

There are many articles which fall in the NTC camp, among them the ZX calculus of Coecke and Duncan from Interacting Quantum Observables: Categorical Algebra and Diagrammatics   arXiv:0906.4725 [quant-ph] , which is a part of the beautiful Categorical Quantum Mechanics. I shall use this article as an anchor which allows to compare with the TC camp. In future posts I shall add more articles to the list, because this is a rather big research field now.

Chemlambda is in the TC camp, like zipper logic.

So let us compare them, concretely.

At first sight they look related, they seem to have the same fundamental genes, say like an elephant (NTC) has almost all genes in common with a mouse (TC). They are both graph rewrites systems, they both use almost the same family of graphs (details later), they both speak about computation:

• in the NTC article case it is about quantum computing, there is also a practical computing arm, the Quantomatic project
• in the TC article case is about distributed, decentralized computing, and there is  the distributed GLC project.

The goals are different, the means are different, the NTC camp is much more developed than the TC camp, the question is:

Is there anything  fundamentally different in the TC camp?

The answer is YES. There are several fundamentally different things in the TC camp, maybe the biggest among them being the different role played by graph rewrites, summarized as NTC vs TC.

Let’s see in more detail, by comparing ZX with chemlambda.

In order to see what is really different, it is useful to make the two formalisms as alike as possible. I shall start by discussing if there is any difference between the graphs which appear in ZX from the ones which appear in chemlambda.

The graphs from ZX don’t have oriented arrows, but instead there is a global orientation convention, say from up to down when represented on page.

In ZX here is also a global horizontal “simultaneity” of graphical elements, which is part of the recipe of associating to a ZX graph an object related to a Hilbert space.

In chemlambda the graphs have oriented arrows. There is no global arrow orientation, nor any horizontal simultaneity.

Otherwise, both in ZX and chemlambda are used loops, free arrows and “half-arrows”.

So, there is an obvious procedure to associate to a graph in chemlambda a graph from ZX, by adding to the graph in chemlambda a global arrow orientation and a horizontal simultaneity.

This means, for example that the graph of the K combinator from chemlambda is represented in ZX like this:

The price is that in ZX there are several new graphical elements which need to be introduced, like the CAP, the CUP and the CROSS. Here is the list of all graphical elements needed to represent chemlambda graphs in ZX.

What about the graph rewrites? Is not clear to me if the chemlambda graph rewrites can be done as finite sequences of ZX graph rewrites, but this is not very important for this discussion. There seems to be anyways a kind of a fundamental alphabet of graph rewrites which keeps appearing everywhere. I shall not be worried about the detailed graph rewrites, but however here is how the FAN-IN and the beta moves from chemlambda appear in ZX translation.

It is worthy to mention that the global arrow orientation and the horizontal simultaneity used in ZX introduces new moves to (the translation of) chemlambda graphs which are related to these constraints, and which are not needed in chemlambda.

Now we are close to see the differences.

There is a recipe for associating to each graph $G$ from ZX an object $O(G)$ on a Hilbert space. This is done by using the global arrow orientation convention and the horizontal simultaneity, along with a dictionary which associates to any graphical element from ZX something from a Hilbert space.

Here is the important thing about the NTC ideology:  if two graphs $G$ and $G'$ have the property that we can go from $G$ to $G'$ by a finite sequence of ZX graph rewrites, then $O(G) = O(G')$.

Each graph $G$ from ZX represents a computation. The graph rewrites from ZX are used to prove that TWO computations are equivalent.

More than this: a graph from ZX represents a computation in the sense that the global arrow orientation is a global time orientation, the horizontal simultaneity express space simultaneity, the CAP is a preparation, the CUP is a measurement. The nodes of the graph are GATES and the arrows of the graph are WIRES which transmit some signals.

That is why, in the NTC camp the graph rewrites DO NOT COMPUTE. The graph rewrites are used to prove an equivalence of two computations, like for example in the case of graphs which represent quantum teleportation protocol.

Now, in chemlambda, a graph is NOT a computation. Each graph is like a chemical molecule, with nodes as atoms and arrows as bonds. There is only one computation in chemlambda, which is done by graph rewrites.

So, even if we can translate chemlambda graphs into ZX graphs, there is this difference.

Suppose $G$ is a ZX graph which is obtained by translating a chemlambda graph, as previously explained. Let $G'$ be another such graph. Suppose that we can arrive from $G$ to $G'$ by a sequence of translations of chemlambda moves (graph rewrites), maybe also by using some of the supplementary “topological” moves which we need in ZX because of the global orientation and simultaneity constraints.

What do we have in ZX?

The graphs $G$ and $G'$ represent two computation which are equivalent.

What do we have in chemlambda?

The graphs $G$ and $G'$ represent the beginning and end of a computation done by the graph rewrites which in ZX serve to prove equivalence of computations.

This very big difference between NTC and TC has a big effect in all the rest of the formalisms.

______________________________________________

# Zipper logic appeared in math.CO (combinatorics)

Today,  a week after the submission, the article Zipper Logic   arXiv:1405.6095 appeared in math.CO , math GT, and not in math.LO , math.GT.

Actually, combinatorics, especially lately, is everywhere, being probably one of the most dynamic research fields in mathematics.

There is a small world connection of zipper logic with combinatorics,   because zipper logic is a variant of chemlambda, which is a variant of GLC, which has an emergent algebra sector  arXiv:1305.5786 section 5 , which is a sort of approximate algebraic structure, alike, but not the same as the approximate groups arXiv:1110.5008 .

____________________________________

# Zipper logic and RNA pseudoknots

UPDATE: compare with the recent Chemlambda strings (working version).

Zipper logic is a variant of chemlambda, enhanced a bit with a pattern identification move called CLICK.

Or, chemlambda is an artificial chemistry.  Does it have a natural, real counterpart?

It should. Finding one is part of the other arm of the research thread presented here, which aims to unite (the computational part of) the real world with the virtual world, moved by the same artificial life/real life basic bricks. The other arm is distributed GLC.

A lot of help is needed for this, from specialists!Thank you for pointing to the relevant references, which I shall add as I receive them.

Further is a speculation, showing that zipper graphs can be turned into something which resembles very much with RNA pseudoknots.

(The fact that one can do universal computation with RNA pseudoknots is not at all surprising, maybe with the exception that one can do functional style programming with these.)

It is a matter of notation changes. Instead of using oriented crossings for denoting zippers, like in the thread called “curious crossings” — the last  post is Distributivity move as a transposition (curious crossings II) — let’s use another, RNA inspired one.

So:

• arrows (1st row) are single stranded RNA pieces. They have a natural 5′-3′ orientation
• termination node (2nd row) is a single strand RNA with a “termination word on it”, figured by a magenta rectangle
• half-zippers are double strands of RNA (3rd and 4th rows). The red rectangle is (a pair of antiparallel conjugate) word(s) and the yellow rectangle is a tag word.

Remark that any (n) half-zipper can be transformed into a sequence of (1) half-zippers, by repeated applications if the TOWER moves, therefore (n) half-zippers appear in this notation like strings of repeated words.

Another interesting thing is that on the 3rd row of the figure we have a notation for the lambda abstraction node and on the 4th row we have one of the application  node form chemlambda. This invites us to transform the other two nodes — fanin and fanout — of chemlambda into double stranded RNA. It can be done like this.

On the first two rows of this picture we see the encoding of the (1) half-zippers, i.e. the encoding of the lambda abstraction and application, as previously.

On the 3rd row is the encoding of the fanout node and on the 4th row the one of the fanin.

In this way, we arrived into the world of RNA. The moves transform as well into manipulations of RNA strings, under the action of (invisible and to be discovered) enzymes.

But why RNA pseudoknots? It is obvious, as an exercise look how the zipper I and K combinators look in this notation.

We see hairpins.

___________________________________

Conclusion:  help needed for chemistry experts. Low hanging fruits here.

___________________________________

# Distributivity move as a transposition (curious crossings II)

It looks that there is a connection of the following with the research on DNA topology, but I shall comment on this in a future post, mainly because I am learning about this right now. (But another main reference is Louis Kauffman.)

Let’s see.

If I am using this encoding of chemlambda nodes with crossings

which is a variant of the encoding from Curious crossings   then, as in the mentioned post,   the beta move becomes a CLICK between “sticky ends” which are marked with dashed lines, followed by R2b move, and also the FAN-IN move becomes a CLICK between sticky ends, followed by a R2a move.

What about the DIST moves? Let’s take the DIST move which involves an application node and a fanout node. The move looks like this:

(Click on the picture to make it bigger.)

In the right column we see the DIST move with chemlambda drawing conventions. In the left column there is the translation with crossings and sticky ends.

What do we see? The strings 1-5 and 6-3 are transposed by the DIST move and a new string appears, which crosses them.

I can draw the same move like this:

In this figure, the left column is as before, but the right column has changed. I just kept the order, from left to right, of the strings 6-3 and 1-5, and I wiggled the string 2-4 for this.

This is starting to look interestingly alike some other pictures from  DNA topology.

___________________________________________

# Curious crossings

I’m coming back to  the post   Halfcross way to pattern recognition (in zipperlogic)    and I am going to modify the drawings a bit.

Instead of this convention of transforming chemlambda nodes into half-crossings

I draw this mapping from chemlambda nodes to crossings:

Remark that at the left we have now crossings. At the right we have the chemlambda nodes, each with a dashed half-arrow attached, so now the nodes become 4-valent locally planar ones.

As usual (here at chorasimilarity) the crossing diagrams are only locally planar!

Look closer: there are two kinds of oriented crossings, right? To each kind corresponds a colour (green or red) of a chemlambda node.

This is no longer a dictionary, there is no longer a bijective correspondence, because for each oriented crossing there are two possible chemlambda nodes, depending on where is the dashed half-arrow! That is the meaning of the wiggling blue arrow from right to left, it’s uni-directional.

OK then, instead of drawing this interpretation of the beta move

we get the following one

where the arrows are drawn like that in order to see what transforms into what (otherwise there is no need for those convoluted arrows in the formalism).

I draw this:

Funny, what could that mean?

________________________________________

# Birth and death of zipper combinators (II)

Continues from   Birth and death of zipper combinators (I).

In the following is presented another mechanism of birth/death of zipper combinators, which is not using a garbage collecting arrow and termination node.

For any zipper combinator $A$ there is a number $n$ and a succession o f$n$ CLICK, ZIP and LOC PRUNING moves such that

So this time   we transform a zipper combinator connected to a termination node into a bunch of loops.

Proof. The first part is identical with the one from the previous post, namely we remark that we can reduce the initial zipper combinator with the exit connected to a termination node into a finite collection of simpler zippers.

This is done by a succession of LOC PRUNING moves for $(+)$ half-zippers.

We shall use then the following succession of moves, in order to “unlock” $(-)$ half-zippers.

If we use this for the $I$ zipper combinator then we can transform it into one loop.

The same trick is used for transforming the zipper combinator $K$ into two loops.

The zipper combinator $S$ is transformed into three loops, starting by the same trick.

The proof is done.

_____________________________

It follows that w can replace garbage collection by ELIM LOOPS, a move which appeared in earlier formulations of chemlambda.

Seen from the birth point of view, if we have enough loops then we can construct any zipper combinator (with the exit arrow connected to a termination node).

_____________________________

# Birth and death of zipper combinators (I)

Because zipper logic is a graph rewriting system which does not use variable names, just like GLC and chemlabda,  it needs ways to multiply, distribute or kill  things.

See  Chemlambda, universality and self-multiplication  for multiplication, distribution or propagation phenomena.

In this post we shall see how zipper combinators die or are born, depending on the sense of reading the moves. This can happen in several ways, one of them explained in this post.

This can also be seen as the statement: we can do garbage collection in chemlambda, GLC or zipper logic.

____________________________________

Zipper combinators.   The set of zipper combinators is the smallest set of zipper graphs with the properties:

•  it contains the S, K, I zipper graphs defined in  the next figure

• for any natural number $n >0$ and for any $n+1$ zipper combinators, the zipper graph obtained by connecting the out arrows of the  zipper combinators to the in arrows of the $(+n)$ half-zipper is a zipper combinator.

• any zipper graph which is obtained by applying a zipper logic move to a zipper combinator is a zipper combinator.

I want to prove that for any zipper combinator $A$, there is a number $n$ and  a succession of $n$  LOCAL PRUNING,  CLICK and ZIP moves such that:

Proof.     Becauseof the LOC PRUNING move satisfied by  \$latex  (+)\$ half-zippers, it follows that by a finite number of these moves we can achieve the effect described in the next figure, for any zipper combinator $A$ (of course, the number of these moves depends on $A$):

It is left to prove that the free arrow ending with a termination node can “eat”, one by one, all the $I, K, S$ zipper combinators.

For the $I$ combinator, it happens like this:

The case of the combinator $K$ is described next:

The combinator $S$ is absorbed by the following succession of moves:

The proof is done.

_____________________________________

We can read all backwards, by saying that an arrow connected to a termination node can give birth to  any zipper combinator, with the out arrow connected to a termination node.

_____________________________________