This is a talk in the Conference on Physical Knotting, Vortices and Surgery in Nature.
This is a talk in the Conference on Physical Knotting, Vortices and Surgery in Nature.
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.
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:
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:
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.
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)
lets do for an epsilon arbitrary the epsilon beta move
— epsilon BETA –>
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…
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 .
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.
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!
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:
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 = 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.
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
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:
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.
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.
As you know, the set of things is the same as the trivial groupoid of things , with arrows being pairs of things and with composition of arrows being . Now, let us define first what is the “space” around one object from T, let’s call it ““. (The same works for each object).
For defining this you take a commutative group (could be or could be the free commutative group over an alphabet (containing for example “NEAR” an “FAR”, such that , etc). Call this group the “scale group”. Then to any pair of objects and any scale , associate a “virtual pair at scale epsilon” , where 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.
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 .