Category Archives: computation

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.

 

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?

Lambda calculus inspires experiments with chemlambda

In the now deleted chemlambda collection I told several stories about how lambda calculus can bring inspiration for experiments with chemlambda. I select for this post a sequence of such experiments. For previous related posts here see this tag and this post.

Let’s go directly to the visuals.

Already in chemlambda v1 I remarked the interesting behaviour of the graph (or molecule) which is obtained from the lambda term of the predecessor applied to a Church number.  With the deterministic greedy algorithm of reductions, after the first stages of reduction there is a repeating pattern of  reduction, (almost) up to the end. The predecessor applied to the Church number molecule looks almost like a closed loop made of pairs A-FO (because that’s how a Church number appears in chemlambda), except a small region which contains the graph of the predecessor, or what it becomes after few rewrites.

In chemlambda v2 we have two kinds of fanouts: FO and FOE.  The end result of the reduction of the same molecule, under the same algorithm, is different: where in chemlambda v1 we had FO nodes (at the end of the reduction), now we have FOE nodes. Other wise there’s the same phenomenon.

Here is it, with black and white visuals

pred

Made by recording of this live (js) demo.

1. What happens if we start not from the initial graph, but from the graph after a short number of rewrites? We have just to cut the “out” root of the initial graph, and some nodes from it’s neighbourhood and glue back, so that we obtain a repeating pattern walking on a circular train track.

Here is it, this time with the random reduction algorithm:

bigpred_train-opt

I previously called this graph an “ouroboros”. Or a walker.

2. That is interesting, it looks like a creature (can keep it’s “presence”) which walks in a single direction in a 1-dimensional world.  What could be the mechanism?

Penrose comes to mind, so in the next animation I also use a short demonstration from a movie by Penrose.

bigpred_penrose-opt

 

3. Let’s go back to the lambda calculus side and recall that the algorithm for the translation of a lambda term to a chemlambda molecule is the same as the one from GLC, i.e the one from Section 3 here. There is a freedom in this algorithm, namely that trees of FO nodes can be rewired as we wish. From one side this is normal for GLC and chemlambda v1,  which have the CO-COMM and CO-ASSOC rewrites

convention_3

In chemlambda v2 we don’t have these rewrites at all, which means that in principle two diferent molecules,  obtained from the same lambda term, which differ only by the rewiring of the FO nodes may reduce differently.

In our case it would be interesting to see if the same is true for the FOE nodes as well. For example, remark that the closed loop, excepting the walker, is made by a tree of FOE nodes, a very simple one. What happens if we perturb this tree, say by permuting some of the leaves of the tree, i.e. by rewiring the connections between FOE and A nodes.

bigpred_train_perm-opt

The “creature” survives and now it walks in a world which is no longer 1 dimensional.

Let’s play more: two permutations, this time let’s not glue the ends of the loop:

bigpred_train_egg

It looks like a signal transduction from the first glob to the second. Can we make it more visible, say by making invisible the old nodes and visible the new ones? Also let’s fade the links by making them very large and almost transparent.

bigpred_train_egg_mist_blue

Signal transduction! (recall that we don’t have a proof that indeed two molecules from the same lambda term, but with rewired FO trees reduce to the same molecule, actually this is false! and true only for a class of lambda terms. The math of this is both fascinating and somehow useless, unless we either use chemlambda in practice or we build chemlambda-like molecular computers.)

4.  Another way to rewire the tree of FOE nodes is to transform it into another tree with the same leaves.

bigpred_tree-opt

 

5. Wait, if we understand how exactly this works, then we realize that we don’t really need this topology, it should also work for topologies like generalized Petersen graphs, for example for a dodecahedron.

dodecahedron_walker

 

This is a walker creature which walks in a dodecaheral “world”.

6. Can the creature eat? If we put something on it’s track, see if it eats it and if it modifies the track, while keeping it’s shape.

walker_bit-opt

So the creature seems to have a metabolism.

We can use this for remodeling the world of the creature. Look what happens after many passes of the creature:

walker_bit_new

 

7. What if we combine the “worlds” of two creatures, identical otherwise. Will they survive the encounter, will they interact or will they pass one through the other like solitons?

bigpred_bif

 

Well, they survive. Why?

8. What happens if we shorten the track of the walker, as much as possible? We obtain a graph wit the following property: after one (or a finite give number of) step of the greedy deterministic algorithm we obtain an isomorphic graph. A quine! chemlambda quine.

At first, it looks that we obtained a 28 nodes quine. After some analysis we see that we can reduce this quine to a 20 nodes quine. A 20-quine.

Here is the first observation of the 20-quine under the random algorithm

20_quine_50steps

According to this train of thoughts, a chemlambda quine is a graph which has a periodic evolution under the greedy deterministic algorithm, with the list of priority of rewrites set to DIST rewrites (which add nodes)  with greater priority than beta and FI-FOE rewrites (which subtract ndoes), and which does not have termination nodes (because it leads to some trivial quines).

These quines are interesting under the random reduction algorithm, which transform them into mortal living creatures with a metabolism.

____________

So this is an example of how lambda calculus can inspire chemlambda experiments, as well as interesting mathematical questions.

An extension of hamiltonian mechanics

This is an introduction to the ideas of the article arXiv:1902.04598

UPDATE: If you think about a billiard-ball computer, the computer is in the expression of the information gap. The model applies  also to chemlambda, molecules have a hamiltonian as well and the graph rewrites, aka chemical reactions, have a description in the information gap. That’s part of the kaleidos project 🙂

__

Hamiltonian mechanics is the mechanism of the world. Indeed, the very simple equations (here the dot means a time derivative)

hamiltonian-1

govern everything. Just choose an expression for the function H, called hamiltonian, and then solve these equations to find the evolution in time of the system.

Quantum mechanics is in a very precise sense the same thing. The equations are the same, only the formalism is different. There is a hamiltonian which gives the evolution of the quantum system…

Well, until measurement, which is an addition to the beautiful formalism. So we can say that hamiltonian mechanics, in the quantum version, and the measurement algorithm are, together, the basis of the quantum world.

Going back to classical mechanics, the same happens. Hamiltonian mechanics can be used as is in astronomy, or when we model the behavior of a robotic arm, or other purely mechanical system. However, in real life there are behaviors which go beyond this. Among them: viscosity, plasticity, friction, damage, unilateral contact…

There is always, in almost all applications of mechanics, this extra ingredient: the system does not only have a hamiltonian, there are other quantities which govern it and which make, most of the time, the system to behave irreversibly.

Practically every  object, machine or construction made by humans needs knowledge beyond hamiltonian mechanics. Or beyond quantum mechanics. This is the realm of applied mathematics, of differential equations, of numerical simulations.

In this classical mechanics for the real world we need the hamiltonian and we also need to explain in which way the object or material we study is different from all the other objects or materials. This one is viscous, plastic, elsot-plastic, elasto-visco-plastic, there is damage, you name it, these differences are studied and they add to hamiltonian mechanics.

They should add, but practically they don’t. Instead, what happens is that the researchers interested into such studies choose to renounce at the beaustiful hamiltonian mechanics formalism and to go back to Newton and add their knowledge about irreversible behaviours there.

(There is another aspect to be considered if you think about mechanical computers. They are mostly nice thought experiments, very powerfull ideas generators. Take for example a billiard-ball computer. It can’t be described by hamiltonian mechanics alone because of the unilateral contact of the balls with the biliard and of the balls one with another. So we can study it, but we have to add to the hamiltonian mechanics formalism.)

From all this  we see that it may be interesting to study if there is any information content of the deviation from hamiltonian mechanics.

We can measure this deviation by a gap vector, defined by

hamiltonian-2

and we need new equations for the gap vector \eta.  Very simple then, suppose we have the other ingredient we need, a likelihood function \pi \in [0,1] and we add that

hamiltonian-3

where z = z(t) = (q(t), p(t)). That is we ask that    if the system is in the state z then the velocity \dot{z} and the gap vector \eta   maximize the likelihood \pi .

Still too general, how can we choose the likelihood? We may take the following condition

hamiltonian-4

that is we can suppose that the algorithm max  gives a  categorical answer when applied to any of the 2nd or 3rd argument of the likelihood.

(It’s Nature’s business to embody the algorithm max…)

We define then the information content associated to the likelihood as

hamiltonian-5

So now we have a principle of minimal information content of the difference from hamiltonian evolution: minimize

hamiltonian-6

 

In arXiv:1902.04598 I explain how this extension of hamiltonian mechanics works wonderfully with viscosity, plasticity, damage and unilateral contact.

[see also this]