Category Archives: computation

Chemlambda and hapax

I wrote an expository text about chemlambda and hapax (and interaction combinators). You can see clearly there how hapax works differently and, as well, clear exposition of several conventions used, about the type of graphs and the differences in the treatment of rewrites.

Chemlambda and hapax

Please let me know if you have any comments.

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.

 

Hapax chemlambda

Chemistry is a game with a pair of dices.

You roll two dices and act. The dices are permutohedra.

Which leads to ask what certain chemistries (artificial or real) have so special. The conjecture is that (probabilistically speaking) a sizeable proportion of them are special.

For example, we can evade the lambda calculus by choosing one of the  14400 rewrites for ( β with random right patterns) .

Hapax chemlambda!

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

__________________________________________

 

Fold rewrite, dynamic DNA material and visual DSD

As it happened with chemlambda programs, I decided it is shorter to take a look myself at possible physical realizations of chemlambda than to wait for others, uninterested or very interested really, people.

Let me recall a banner I used two years ago

KeepCalmStudio.com-Shortest-Explanation-Of-Chemlambda-[Knitting-Crown]-Keep-Calm-And-Use-Rna-For-Interaction-Nets

It turns out that I know exactly how to do this. I contacted Andrew Phillips, in charge with Microsoft’ Visual DSD  with the message:

Dear Andrew,

I am interested in using Visual DSD to implement several graph-rewriting formalisms with strand graphs: Lafont Interaction Combinators, knots, spin braids and links rewrite systems, my chemlambda and emergent algebra formalisms.

AFAIK this has not been tried. Is this true? I suggest this in my project chemlambda but I don’t have the chemical expertise.

About me: geometer working with graph rewrite systems, homepage: http://imar.ro/~mbuliga/index.html or
https://mbuliga.github.io/

Some links (thank you for a short reception of the message reply):

Chemlambda:
– github project: https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/README.md
– page with more links: http://imar.ro/~mbuliga/chemlambda-v2.html
– arXiv version of my Molecular computers article https://arxiv.org/abs/1811.04960

Emergent algebras:
– em-convex https://arxiv.org/abs/1807.02058

 

I still wait for an answer, even if Microsoft’ Washington Microsoft Azure and Google Europe immediately loaded the pages I suggested in the mail.

Previously, I was noticed by somebody [if you want to be acknowledged then send me a message and I’ll update this] about Hamada and Luo Dynamic DNA material with emergent locomotion behavior powered by artificial metabolism  and I sent them the following message

Dear Professors Hamada and Luo,

I was notified about your excellent article Dynamic DNA material with emergent locomotion behavior powered by artificial metabolism, by colleagues familiar with my artificial chemistry chemlambda.

This message is to make you aware of it. I am a mathematician working with artificial chemistries and I look for ways to implement them in real chemistry. The shortest description of chemlambda is: an artificial chemistry where the chemical reactions are alike a Turing complete family of graph rewrites.

If such a way is possible then molecular computers would be not far away.

Here is a list of references about chemlambda:

– GitHub repository with the scripts https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/README.md
– page which collects most of the resources http://imar.ro/~mbuliga/chemlambda-v2.html

Thank you for letting me know if this has any relation to your interests. For my part I would be very thrilled if so.

Best regards,
Marius Buliga

Again, seems that these biology/chemistry people have problems with replies to mathematicians, but all ths makes me more happy because soon I’ll probably release instructions about how everybody could make molecular computers along the lines of Molecular computers.

I’ll let you know if there are future “inspiration” work. Unrelated to chemlambda, there are several academic works which shamelessly borrow from my open work without acknowledgements, I’ll let you know about these and I’ll react in more formal ways. I hope though this will not be the case with chemlambda, however, this happened before twice at least.  (I say nothing about enzymes/catalysts, category theory and cryptocurrencies… for the moment.)

Finally, here is a realization of the lambda calculus beta rewrite via a FOLD rewrite

arrowlink-2

which shares a relation with the ZIP rewrite from Zipper Logic. It seems I was close to reality,  now though I got it exactly 🙂 .

Let’s talk soon!

 

 

 

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.