Tag Archives: small graph rewrite systems

What is the purpose of the project Hapax?

“hapax” means “only once” in ancient Greek. You may have seen it in the form hapax legomenon, quote: ” a word that occurs only once within a context, either in the written record of an entire language, in the works of an author, or in a single text”.

After a bit of research I found the correct, I hope, form that I  use for this project:

apaxcheon

It reads “hapax cheon” and it means, again in ancient Greek, “poured only once”.

Why this? Because, according to this wiki link, “the Greek word χυμεία khumeia originally meant “pouring together””.

The motivation of the project hapax comes from the realization that we only explored a tiny drop in the sea of possibilities. As an example, just look at lambda calculus, one of the two pillars of computation. Historically there are many reasons to consider lambda calculus something made in heaven, or a platonic ideal.

But there are 14400 = 5! X 5! alternatives to the iconic beta rewrite only. Is the original beta special or not?

By analogy with the world of CA, about a third of cellular automata are Turing universal. My gues is that a significant fraction of the alternatives to the beta rewrite are as useful as the original beta.

When we look at lambda calculus from this point of view, we discover that all the possible alternatives, not only of beta, but of the whore graph rewriting formalism, say in the form of chemlambda, all these alternative count a huge number, liek 10^30 in the most conservative estimates.

Same for interaction combinators. Same for knot theory. Same for differential calculus (here I use em).

I started to collect small graph rewrite systems which can be described with the same formalism.

The formalism is based on a formulation which uses exclusively permutations (for the “chemistry”  and Hamiltonian mechanics side) and a principle of dissipation which accounts for the probabilistic side.

The goal of the project hapax is to build custom worlds (physics and chemistry)

“poured only once”

which can be used to do universal computation in a truly private way. Because once the rules of computation are private,  this leads to the fact that the who;le process of computation becomes incomprehensible.

Or is it so? Maybe yes, maybe not. How can we know, without trying?

That is why I starded to make the hapax stuff.

For the moment is not much, only demos like this one, but the rest will pass from paper to programs, then we’ll play.

 

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.

marked-graphs

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.

marked-graphs-1

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.

marked-graphs-2

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.

marked-graphs-4

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

__________________________________________

 

Small graph rewrite systems (5)

Here are some more tentative descriptions of system X and a play with the trefoil knot. This post comes after the intermezzo and continues the series on small graph rewrite systems.

Recall that system X is a proposal to decompose a crossing into two trivalent nodes, which transforms a knot diagram into an unoriented stick-and-ring graph.

2cols-spin-x

The rewrites are the following, written both with the conventions from the stick-and-ring graphs and also with the more usual conventions which resemble the slide equivalence or spin braids mentioned at the intermezzo.

The first rewrite is GL (glue), which is a Reidemeister 1 rewrite in only one direction.

2cols-spin-gl-x

The second rewrite is RD2, which is a Reidemeister 2 rewrite in one direction.

2cols-spin-rd2-x

There is a DIST rewrite, the kind you encounter in interaction combinators or in chemlambda.

2cols-spin-dist-x

And finally there are two SH rewrites, the patterns as in chemlambda or appearing in the semantics of interaction combinators.

2cols-spin-sh1-x

2cols-spin-sh2-x

One Reidemeister 3 rewrite appears from these ones, as explaned in the following figure (taken from the system X page).

2cols-spin-rd3

Let’s play with the trefoil knot now. The conversion to stick-and rings

2cols-spin-3foil

is practically the Gauss code. But when we apply some sequences of rewrites

2cols-spin-3f-2

we obtain more complex graphs, where

  • either we can reverse some pairs of half-crossings into crossings, thus we obtain knotted Gauss codes (?!)
  • or we remark that we get fast out of the Gauss codes graphs…

thus we get sort of a recursive Gauss codes.

Finally, remark that any knot diagram has a ring into it. Recall that lambda terms translated to chemlambda don’t have rings.

Small graph rewrite systems (4)

This post follows Problems with slide equivalence. A solution is to replace slide equivalence with System X.

This supposes to change the decomposition of a crossing like this:

2cols-spin-conv

I let you discover system X (or will update later) but here I want to show you that the Reidemeister 3 rewrite looks like that:

2cols-spin-rd3

There is now a page dedicated to small graph rewrite systems and stick-and-rings graphs.

 

Problems with slide equivalence

UPDATE: System X is a solution.

_________

After the Intermezzo, in this post I’ll concentrate on the slide equivalence for unoriented (virtual) links, as defined in L.H. Kauffman, Knots and Physics, World Scientific 1991, p. 336.

slideq

 

Later on we shall propose a small graph rewrite system which is different from this, but we first need to understand that there are some problems with slide equivalence.

Kauffman rule I’ is half a definition, half a rewrite rule. He gives two decompositions of a crossing into two 3-valent nodes. The rewrite is that we can pass from one decomposition to the other.

Problem 1. How many types of 3-valent nodes are used? My guess is just one.

q1

Problem 2. Is the rule II’ needed at all? Why not use instead the rule III’, with the price of a loop:

q2

Problem 3. Is the rule I’ too strong? Maybe, look at the following configuration made of two crossings.

q3

Neighboring crossings dissappear.

We don’t even need two neighboring crossings. In the next figure I took the left pattern from the rule IV’, first part. It is also a pattern where the rules I’, then III’ apply.

q4

The result is very different from the application of IV’.

The same happens for the right pattern of the rule IV’, first part.

q5

We can use again I’ and III’ to obtain a very different configuration than expected.

 

Conclusion.  The slide equivalence rewrites with a “dumb” algorithm of rewrites application behaves otherwise than expected. By “dumb” I mean my favorite algorithms, like greedy deterministic or random.

Used with intelligence, the slide equivalence rewrites have interesting computational aspects, but what about the “intelligent” algorithm? Kauffman brains are rare.

 

 

Intermezzo (small graph rewrite systems)

Between the last post on small graph rewrite systems and a new one to follow, here are some other, real world examples of such systems.

Where is this from? Answer: M. Khovanov,   New geometrical constructions in low-dimensional topology, preprint 1990, fig. 20

spinb

Where is this from? Answer: L.H. Kauffman, Knots and Physics, World Scientific 1991, p. 336.

slideq

How can we put this in order?

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:

lafont-2

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

a-l

fi-foe

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:

2cols-sh

 

2cols-gl

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

2cols-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.

2cols-rm-from-r2

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

2cols-rm

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.