# 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. __________________________________________

# More detailed argument for the nature of space buillt from artificial chemistry

There are some things which were left uncleared. For example, I have never suggested to use networks of computers as a substitute for space, with computers as nodes, etc. This is one of the ideas which are too trivial. In the GLC actors article is proposed a different thing.

First to associate to an initial partition of the graph (molecule) another graph, with nodes being the partition pieces (thus each node, called actor, holds a piece of the graph) and edges being those edges of the original whole molecule which link nodes of graphs from different partitions. This is the actors diagram.
Then to interpret the existence of an edge between two actor nodes as a replacement for a spatial statement like (these two actors are close). Then to remark that the partition can be made such that the edges from the actor diagram correspond to active edges of the original graph (an active edge is one which connects two nodes of the molecule which form a left pattern), so that a graph rewrite applied to a left pattern consisting of a pair of nodes, each in a different actor part, produces not only a change of the state of each actor (i.e. a change of the piece of the graph which is hold by each actor), but also a change of the actor diagram itself. Thus, this very simple mechanism produces by graph rewrites two effects:

• “chemical” where two molecules (i.e. the states of two actors) enter in reaction “when they are close” and produce two other molecules (the result of the graph rewrite as seen on the two pieces hold by the actors), and
• “spatial” where the two molecules, after chemical interaction, change their spatial relation with the neighboring molecules because the actors diagram itself has changed.

This was the proposal from the GLC actors article.

Now, the first remark is that this explanation has a global side, namely that we look at a global big molecule which is partitioned, but obviously there is no global state of the system, if we think that each actor resides in a computer and each edge of an actor diagram describes the fact that each actor knows the mail address of the other which is used as a port name. But for explanatory purposes is OK, with the condition to know well what to expect from this kind of computation: nothing more than the state of a finite number of actors, say up to 10, known in advance, a priori bound, as is usual in the philosophy of local-global which is used here.

The second remark is that this mechanism is of course only a very
simplistic version of what should be the right mechanism. And here
enter the emergent algebras, i.e. the abstract nonsense formalism with trees and nodes and graph rewrites which I have found trying to
understand sub-riemannian geometry (and noticing that it does not
apply only to sub-riemannian, but seems to be something more general, of a computational nature, but which computation, etc). The closeness,  i.e. the neighbourhood relations themselves are a global, a posteriori view, a static view of the space.

In the Quick and dirty argument for space from chemlambda I propose the following. Because chemlambda is universal, it means that for any program there is a molecule such that the reductions of this molecule simulate the execution of the program. Or, think about the chemlambda gui, and suppose even that I have as much as needed computational power. The gui has two sides, one which processes mol files and outputs mol files of reduced molecules, and the other (based on d3.js) which visualizes each step. “Visualizes” means that there is a physics simulation of the molecule graphs as particles with bonds which move in space or plane of the screen. Imagine that with enough computing power and time we can visualize things in as much detail as we need, of course according to some physics principles which are implemented in the program of visualization. Take now a molecule (i.e. a mol file) and run the program with the two sides reduction/visualization. Then, because of chemlambda universality we know that there exist another molecule which admit chemlambda reductions which simulate the reductions of the first molecule AND the running of the visualization program.

So there is no need to have a spatial side different from the chemical side!

But of course, this is an argument which shows something which can be done in principle but maybe is not feasible in practice.

That is why I propose to concentrate a bit on the pure spatial part. Let’s do a simple thought experiment: take a system with a finite no of degrees of freedom and see it’s state as a point in a space (typically a symplectic manifold) and it’s evolution described by a 1st order equation. Then discretize this correctly(w.r.t the symplectic structure)  and you get a recipe which describes the evolution of the system which has roughly the following form:

• starting from an initial position (i.e. state), interpret each step as a computation of the new position based on a given algorithm (the equation of evolution), which is always an algebraic expression which gives the new position as a  function of the older one,
• throw out the initial position and keep only the algorithm for passing from a position to the next,
• use the same treatment as in chemlambda or GLC, where all the variables are eliminated, therefore renounce in this way at all reference to coordinates, points from the manifold, etc
• remark that the algebraic expressions which are used  always consists  of affine (or projective) combinations of  points (and notice that the combinations themselves can be expressed as trees or others graphs which are made by dilation nodes, as in the emergent algebras formalism)
• indeed, that  is because of the evolution equation differential  operators, which are always limits of conjugations of dilations,  and because of the algebraic structure of the space, which is also described as a limit of  dilations combinations (notice that I speak about the vector addition operation and it’s properties, like associativity, etc, not about the points in the space), and finally because of an a priori assumption that functions like the hamiltonian are computable themselves.

This recipe itself is alike a chemlambda molecule, but consisting not only of A, L, FI, FO, FOE but also of some (two perhaps)  dilation nodes, with moves, i.e. graph rewrites which allow to pass from a step to another. The symplectic structure itself is only a shadow of a Heisenberg group structure, i.e. of a contact structure of a circle bundle over the symplectic manifold, as geometric  prequantization proposes (but is a mathematical fact which is, in itself, independent of any interpretation or speculation). I know what is to be added (i.e. which graph rewrites which particularize this structure among all possible ones). Because it connects to sub-riemannian geometry precisely. You may want to browse the old series on Gromov-Hausdorff distances and the Heisenberg group part 0, part I, part II, part III, or to start from the other end The graphical moves of projective conical spaces (II).

Hence my proposal which consist into thinking about space properties as embodied into graph rewriting systems, inspred from the abstract nonsense of emergent algebras, combining  the pure computational side of A, L, etc with the space  computational side of dilation nodes into one whole.

In this sense space as an absolute or relative vessel does not exist more than the  Marius creature (what does exist is a twirl of atoms, some go in, some out, but is too complex to understand by my human brain) instead the fact that all beings and inanimate objects seem to agree collectively when it comes to move spatially is in reality a manifestation of the universality of this graph rewrite system.

Finally, I’ll go to the main point which is that I don’t believe that
is that simple. It may be, but it may be as well something which only
contains these ideas as a small part, the tip of the nose of a
monumental statue. What I believe is that it is possible to make the
argument  by example that it is possible that nature works like this.
I mean that chemlambda shows that there exist a formalism which can do this, albeit perhaps in a very primitive way.

The second belief I have is that regardless if nature functions like this or not, at least chemlambda is a proof of principle that it is possible that brains process spatial information in this chemical way.

__________________________________________________________________

# How not to do the beta move: use emergent algebra instead

In the frame of chemlambda and g-patterns, here is how not to do the beta move. We pass from chemlambda to a slightly enlarged version, see the graphical formalism of projective conical spaces, which would correspond to an only local moves version of the whole GLC, with the emergent algebra nodes and moves.

Then we do emergent algebra moves instead.

Look, instead of the beta move (see here all moves with g-patterns)

L[a,d,k] A[k,b,c]

<–BETA–>

Arrow[a,c] Arrow[b,d]

lets do for an epsilon arbitrary the epsilon beta move Remark that I don’t do the beta move, really. In g-patterns the epsilon beta move does not replace the LEFT pattern by another, only it ADDS TO IT.

L[a,d,k] A[k,b,c]

— epsilon BETA –>

FO[a,e,f]  FO[b,g,h]

L[f,i,k] A[k,h,j]

epsilon[g,i,d] epsilon[e,j,c]

Here, of course,  epsilon[g,i,d] is the new graphical element corresponding to a dilation node of coefficient epsilon.

Now, when epsilon=1 then we may apply only ext2 move and LOC pruning (i.e. emergent algebra moves) and we get back the original g-pattern.

But if epsilon goes to 0 then, only by emergent algebra moves: that’s it the BETA MOVE is performed!

What is the status of the first reduction from the figure? Hm, in the figure appears a node which has a “0” as decoration. I should have written instead a limit when epsilon goes to 0… For the meaning of the node with epsilon=0 see the post Towards qubits: graphic lambda calculus over conical groups and the barycentric move. However, I don’t take the barycentric move BAR, here, as being among the allowed moves. Also, I wrote “epsilon goes to 0”, not “epsilon=0”.

__________________________________________________________

epsilon can be a complex number…

__________________________________________________________

Questions/exercises:

• the beta move pattern is still present after the epsilon BETA move, what happens if we continue with another, say a mu BETA move, for a mu arbitrary?
• what happens if we do a reverse regular BETA move after a epsilon beta move?
• why consider “epsilon goes to 0” instead of “epsilon = 0”?
• can we do the same for other moves, like DIST, for example?

__________________________________________________________

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

____________________________________

# The graphical moves of projective conical spaces (II)

Continues from  The graphical moves of projective conical spaces (I).

In this post we see the list of moves.

The colours X and O are added to show that the moves preserve the class of graphs PROJGRAPH.

The drawing convention is the following:  columns of colours represent possible different choices of colouring. In order to read correctly the choices, one should take, for example, the first elements from all columns, as a choice, then the second element from all columns, etc. When there is only one colour indicated, in some places, then there is only one choice for the respective arrow. Finally, I have not added symmetric choices obtained by replacing everywhere X by O and O by X.

1. The PG move. As you see, there is only one PG move. There are 3 different choices of colours, which results into 3 versions of the PG move, as explained in the post A simple explanation with types of the hexagonal moves of projective spaces.

2. The DIST move. This is the projective version of the “mystery” move which appeared in the posts

Look at  the chemlambda DIST moves to see that this move is in the same family.

3. The R1 move. This is a projective version of the GLC move R1 (more precisely R1a). The name comes from “Reidemeister 1” move, as seen through the lens of emergent algebras.

4. The R2 move. This is a projective version of the GLC move R2 . The name comes from “Reidemeister 2” move.

5. The ext2 move. This is a projective version of the GLC move ext2.

6. CO-COMM, CO-ASSOC and LOC PRUNING.  These are the usual  moves  associated to the fanout node. The LOC PRUNING move for the dilation node is also clear.

_____________________________

All these moves are local!

_____________________________

# The graphical moves of projective conical spaces (I)

This post continues from A simple explanation with types of the hexagonal moves of projective spaces .  Here I put together all the story of projective conical spaces, seen as a graph rewriting system, in the same style as (the emergent algebra sector of) the graphic lambda calculus.

What you see here is part of the effort to show that there is no fundamental difference between geometry and computation.

Moreover, this graph rewriting system can be used, along the same lines as GLC and chemlambda, for:

•  artificial chemistry
• a model for distributed computing
• or for thinking about an “ethereal” spatial substrate of the Internet of Things, realized as a very low level (in terms of resources needs) decentralized computation,

simply by adapting the Distributed GLC  model for this graph rewriting system, thus transforming the moves (like the hexagonal moves) into interactions between actors.

_________________________________________

All in all,  this post (and the next one) completes the following list:

______________________________________

1. The set of “projective graphs” PROJGRAPH.  These graphs are made by a finite number of nodes and arrows, obtained by assembling:

•  4 valent nodes called (projective) dilations (nodes), with 3 arrows pointing to the node and one arrow pointing from the node. The set of 4 arrows is divided into

4 = 3+1

with 1 incoming arrow and the remaining 3 (two incoming and 1 outcoming) . Moreover, there is a cyclical order on those 3 arrows.

• Each dilation node is decorated  by a Greek letter like $\varepsilon, \mu, ...$,  which denotes an element of a commutative group $\Gamma$. The group operation of $\Gamma$ is denoted multiplicatively.  Usual choices for $\Gamma$ are the real numbers with addition, or the integers with addition, or the positive numbers with multiplication. But any commutative group will do.
• arrows which don’t point to, or which don’t come from any nodes are accepted
• as well as loops with no node.
• there are also 3 valent nodes, called “fanout nodes”, with one incoming arrow and two outcoming arrows, along with a cyclic order of the arrows (thus we know which is the outcoming left arrow and which is the outcoming right arrow).
• moreover, there is a 1-valent termination node, with only 1 incoming arrow.

Sounds like a mouthful?  Let’s think like this: we can colour the arrows of the 4 valent dilation nodes with two colours, such that

• both colours are used
• there are 2 more incoming arrows coloured like the outcoming arrow.

I shall call this colours “O” and “X”,  think about them as being types, if you want. What matters is when two colours are equal or different, and not which colour is “O” and which is “X”.

From this collection of graphs we shall choose a sub-collection, called PROJGRAPH, of “projective graphs”, with the property that we can colour all the arrows of such a graphs, such that:

• the 3 arrows of a fanout node are always coloured with the same colour (no matter which, “O” or “X”) • the 4 arrows of a 4 valent dilation node are coloured such that the special 1 incoming arrow is coloured differently than the other 3 arrows.

With the colour indications, we can simplify the drawing of the 4 valent nodes, like indicated in the examples from this figure. Thus, the condition that a graph (made of 4 valent and 3 valent nodes) is in PROJGRAPH is global. That means that there is no  a priori upper bound on the number of nodes and arrows which have to be checked by an  algorithm which determines if the graph is in PROJGRAPH.

In the next post we shall see the moves, which are all local.

________________________________

# Computing with space in the internet of things

My primary interest is “computing with space”.  Some remarks by  Allen Francom  make me believe that it might be a way to give a “space” to the internet of things by using graphic lambda calculus. By that I mean the following: the internet of things is a huge collection of objects which are somewhere on Earth, each carrying a very small processor. So the objects are in the physical space, but they change their places all the time, and their processors are tiny, so one better use tiny programs and simple executions for syncronizing their relative places one with respect to the others.

That is a kind of “computing with space” and it fits well with the following problem with e-books raised by  by Mark Changizi, who says that  e-books lack space and gives as an example his (physical library). He says he knows that book A is the one close to that calculus book he uses when he need some formulae, and that’s the way he is going to find book A. While, in a virtual library there is no space, the relative positions of a e-book wrt to others is irrelevant, because when you click a link is like you teleport (and ignore space) from one place to another. My interpretation of this is: the way Changizi finds a book in his library is different from the way a robot Changizi would find the book, because the robot Changizi would need the coordinates of the book A with respect to  a corner of the bookshelf, or some information like this, then it would go and fetch the book. On the contrary, the human Changizi (‘s brain) acquired a geometric competence by accumulating these simple bits of knowledge about his library, namely tht book A is near the calculus book, and the calculus book is used when he needs formulae, etc.

Is this a problem which the internet of things will have? Surely. Is this solved? I have no idea, but I know how to solve it, by satisfying also the “tiny programs and executions” constraint. This involves exactly that part (called by me “emergent algebra sector”) which gives the kind of programs for using space in a very concentrated form, not needing “geometric expertise” to generate and manipulate them. Then, imagine that each object from the internet of things has a relative representation of some  of his neighbours, under the form of a small graph, like the graphs from graphic lambda calculus or the molecules from the chemical concrete machine. These graphs are generated from simple rules concerning proximity relations (like the keys thing is on the couch thing, or the socks thing is in the drawer thing), more on that later, and changes in proximity relations are like moves acting on such tiny graph molecules. Then, if you want to know where you lost the keys thing, instead of endowing the keys with a GPS, you just need to evaluate (i.e. decorate, like in the discussions about decorations of graphic lambda calculus graphs) these tiny graphs and find out that the key thing is i the drawer thing.
Here is a more mathematical explanation. Suppose you have a set $T$ of things, objects. You want to describe how they are in space without eventually using any “geometric expertise” (like using a GPS coordinate system, for example).

As you know, the set of things $T$ is the same as the trivial groupoid of things $T^{2}$, with arrows being pairs of things $(a,b)$ and with composition of arrows being $(a,b)(b,c) = (a,c)$.  Now, let us define first what is the “space” around one object from T, let’s call it “ $e$“. (The same works for each object).

For defining this you take a commutative group (could be $(0,\infty)$ or could be the free commutative group over an alphabet (containing for example “NEAR” an “FAR”, such that $NEAR^{-1} = FAR$, etc). Call this group the “scale group”. Then to any pair of objects $(a,b)$ and any scale $\varepsilon$, associate a “virtual pair at scale epsilon” $(a,b)_{\varepsilon} = (b(\varepsilon)a, b)$, where $b(\varepsilon)a$  is like a term in lambda calculus constructed from variable names “a” and “b”, only that it does not satisfy the lambda calculus definition, but the emergent algebra definition. Of course you can see such terms as graphs in graphic lambda calculus made by the epsilon gates, along with the emergent algebra moves from graphic lambda calculus, as in

Moreover, you can mix them with lambda calculus terms, as it is possible in graphic lambda calculus.

So we have (in our platonic universe, because in practice we can’t “have” an infinite set of all things possible) a collection of term-like objects made from a, b, etc and from scales epsilon, mu, etc. We may imagine them visually either as binary trees, like when we represent graphically compositions of operations,
or as graphs in graphic lambda calculus, if we apply to them the algorithm for eliminating variable names. This is a kind of collection of all programs for using a space (each one is a me for space). (Mind you that there is no constraint, like euclidean space, or other.) The space around one object, say e, is obtained from this construction applied to the groupoid of pairs of pairs with arrows $((a,e),(b,e))$  and the scale acts like this $((a,e),(b,e))_{\varepsilon} = ((a,e)_{\varepsilon}, (b,e)_{\varepsilon})$.  (Remark: in the epsilon deformed groupoid the composition of arrows is transported by the epsilon deformation, so the composition changed from trivial to more interesting.)
If you are still reading this and is too long, the shorter description is that the space around an object e is defined in terms of virtual geometric relations (mes for space)  between all the other things from the set $T$ (which is finite, of course), with respect to $latex e$, and that each such virtual geometric relation is a small graph in graphic lambda calculus. More than this, suppose you want to translate from a virtual geometric relation to another (or from a virtual place to another). Such a “translation” is itself a small graph, actually made by only 4 nodes.
And here comes the final part: in order to know where the things from $T$ are, one with respect to the others, it is enough to give,  to attribute to each pair of objects $(a,b)$ a “virtual geometric relation” in the space around $b$, i.e. a graph. If the things move one with respect  to the other, they can update their relative geometric relations by moves in graphic lambda calculus.
If you want to know where a thing is in the physical space then you have to start from somewhere (some object) and decorate the virtual space relations,as they appear as graphs. This is like evaluations of  lambda calculus terms.

In conclusion, I am very interested in practical applications of this, and I can at least formulate a list of needs, some of them with an IT flavour, others applied math. As for the pure math needs, they are pure fun and play. All this together would lead to really interesting things. One of the things to keep in mind is that would also endow the internet of things with a synthetic chemical connectome, as an extension of The chemical connectome of the internet .

___________________________