Universality of interaction combinators and chemical reactions

In the foundational article Interaction combinators, Yves Lafont describes interaction rules as having the form

He then gives three examples of particular families of interaction rules which can be used to simulate Turing Machines, Cellular Automata and Unary Arithmetics.

The main result of his article (Theorem 1) is that there is an algorithm which allows to translate any interaction system (i.e. collection of interaction rules which satisfy some natural conditions) into the very simple system of his interaction combinators:

In plain words, he proves that there is a way to replace the nodes of a given interaction system by networks of interaction combinators in such a way that any of the interaction rules of that interaction system can be achieved (in a finite number of steps) by the interaction rules of the interaction combinators.

Because he has the example of Turing Machines as an interaction system, it follows that the interaction combinators are universal in the Turing sense.

The most interesting thing for me is that Lafont has a notion of universality for interaction systems, the one he uses in his Theorem 1. This universality of interaction combinators is somehow larger than the universality in the sense of Turing. It is a notion of universality at the level of graph rewrite systems, or, if you want, at the level of chemical reactions!

Indeed, why not proceed as in chemlambda and see an interaction rule as if it’s a chemical reaction? We may add an “enzyme” per interaction rule, or we may try to make the reaction conservative (in the number of nodes and wires) as we did in chemlambda strings.

Probably the rewrites of chemlambda are also universal in the class of directed interaction networks. If we take seriously that graph rewrites are akin to chemical reactions then the universality in the sense of Lafont means, more or less:

“any finite collection of chemical reactions among a finite number of patterns of chemical molecules can be translated into reactions among chemlambda molecules”

But why keep talking about chemlambda and not about the original interaction combinators of Lafont. Let’s make the same hypothesis as in the article Molecular computers and deduce that:

such molecular computers which embody the interaction combinators rewrites as chemical reaction can indeed simulate any other finite collection of chemical reactions, in particular life.

For me that is the true meaning of Lafont universality.

Advertisements

Kaleidoscope

Unexpectedly and somehow contrary to my fresh posting about my plans for 2019, during the week of Jan 7-12, 2019 a new project appeared, which is temporary named Kaleidoscope. [Other names, until now: kaleidos, morphoo. Other suggestions?]

This post marks the appearance of the project in my log. I lost some time for a temporary graphical label of it:

I have the opinion that new, very promising projects need a name and a label, as much as an action movie superhero needs a punchline and a mask.

So what is the kaleidoscope? It is as much about mechanical computers (or physically embedded computation) as it is about graph rewrite systems and about space in the sense of emergent algebras and about probabilities. It is a physics theory, a computation model and a geometry in the same time.

What can I wish more, research wise?

Yes, so it deserves to be tried and verified in all details and this takes some time. I do hope that it will survive to my bugs hunt so that I can show it and submit it to your validation efforts.

 

Twitter lies: my long ago deleted account appears as suspended

9 months ago I deleted my Twitter account, see this post.  Just now I looked to see if there are traces left. To my surprise I get the message:

“This account has been suspended. Learn more about why Twitter suspends accounts or return to your timeline.”

See for yourself: link.

This is a lie. I feel furious about the fact that this company shows a misleading information about me, long after I deleted my account.

Projects for 2019 and a challenge

It’s almost the end of 2018, so I updated my expectations post from a year ago, you may find it interesting.

Now, here is a list of projects which are almost done on paper and which deserve attention or reserve some surprises for 2019. Then a challenge for you, dear creative reader.

• I mentioned Hydrogen previously. This is a project to build a realistic hydrogen atom purely in software. This means that I need a theory (a lambda calculus like) for state spaces, then for quantum mechanics and finally for a hydrogen atom.
• Space is of special interest (and needed to build hydrogen), a lambda calculus for space is proposed in the em project. Now I am particularly fascinated by numbers.
• The needs project is a bridge towards chemlambda.  It’s entirely written, in pieces, it is about permutation automata. Only the main routine is public.
• And what would life be without luck, aka computable probabilities? This is the least advanced project, for the moment it covers some parts of classical mechanics, but it is largely feasible and a pleasure to play with it in the year to come.

 

I have a strong feeling that these projects look very weird to you, so I have a proposal and a challenge. The proposal for you is to ask for details. I am willing to give as much as (or perhaps more than) you need.

The challenge is the following.  As you know my banner is “can do anything”.  So let’s test it:

• propose a subject of research where you are stuck. Or better, you want to change the world (in a good way).
• I’ll do something about it as quick as possible, if you get me interested.
• Then I’ll ask for means. And for fairness.
• Then we’ll do it to the best of our capacities.

Well, happy 2019, soon!

 

More experiments with the dynamic GoI abstract machine visualiser and chemlambda

This post continues from Diagrammatic execution models (Lambda World Cadiz 2018) compared with chemlambda . For the context, I quote from  this MonkeyPatchBlog post

“Koko Muroya and Steven Cheung, working under the direction of Dan Ghica, gave a fantastic overview of their work on diagrammatic execution model.  […] There is a nice demo of their work hosted on github”

The demo is the “GoI Visualiser”. In this post I continue to play with this visualiser and with chemlambda as well.

You can play too by using the link to the GoI Visualiser demo and an archive available here, which contains all is needed for running chemlambda and for producind anything from this post.

There is a readme.txt inside which you may enjoy, with instructions to use and some background.

OK, let’s play.

The Goi Visualiser comes with the untyped lambda term

A = ((λf. λx. f (f x)) ((λy. y) (λz. z))) (λw. w)

and in the preceding post I reduced this term in chemlambda. Now I take this term and remark that there are inside 3 identity terms: (λy. y) , (λz. z) and (λw. w). That is why I take the term

B = (λu.(((λf.λx.f(fx))(uu))u))(λw.w)

which has the property that by one BETA reduction it becomes A.

I filmed the reduction of B with the call-by-need, in the GoI Visualiser:

and, out of curiosity, remarked that call-by-name does not work actually it does but I misunderstood what I see!

 

What about chemlambda? The “molecule” (i.e. chemlambda graph) for the lambda term B can be either goi-5.mol, i.e.

A out2 in2 out3
L out in1 out2
A 1 2 out
A 3 4 1
L 5 f 3
FO f 7 9
A 7 8 6
A 9 x 8
L 6 x 5
A 10 11 4
FO in1 2 13
FO 13 10 11
L w w in2

or the goi-6.mol, i.e.

A out2 in2 out3
L out in1 out2
A 1 2 out
A 3 4 1
L 5 f 3
FO f 7 9
A 7 8 6
A 9 x 8
L 6 x 5
A 10 11 4
FO in1 13 2
FO 13 10 11
L w w in2

These two molecules differ in only one place:

FO in1 2 13  (goi-5.mol)   vs.  FO in1 13 2  (goi-6.mol)

Everything is in the archive! Go check for yourself, please 🙂

This difference is due to the fact that the algorithm for building a chemlambda molecule from a lambda term leaves freedom for the way to duplicate variables. Here in the case of the term B, this freedom is in relation with the variable “u”.  Indeed

B = (λu. … (uu))u) …

and to produce 3 u’s from one we need two FO (fanout) nodes, but we may arrange them in two ways.

The algorithm is the one to be expected, here the one from section 3, M. Buliga, Graphic lambda calculus, Complex Systems 22, 4 (2013), 311-360, arXiv:1305.5786.  In chemlambda we transform terms from lambda calculus by this algorithm, but mind that in Graphic Lambda Calculus (GLC) there is only one fanout node, the FO. In chemlambda there are two fanout nodes, the FO and the FOE. What is interesting is that there are no other nodes but the fanin FI, two fanouts FO, FOE, application A, lambda L, arrow Arrow, free input FRIN, free output FROUT, termination T. There are no brackets, boxes, tags!

You want to see again the rewrites of chemlambda? arXiv:1811.04960

So the algorithm of conversion is the one from GLC, with only FO nodes in the initial molecule for the term. There are two possible ways to convert the term B, these are goi-5.mol and goi-6.mol.

The goi-6.mol behaves very cool all the time (i.e. under the random reduction algorithm of chemlambda)

 

The goi-5.mol behaves very well in about 87.5% cases (i.e. in 7/8 cases), from experiments. In most of the cases the reduction ends with an identity, as it should, but in 1/8 cases we end with this siamese brothers identity:

 

which is in mol notation:

FI 1 2 out

L z z 1

L v v 2

i.e. a fanin FI is left alone and it does not know that his left and right inputs are the same.

Why is that?

From all examples where I reduced molecules from lambda terms, I encountered this phenomenon only once, see the story of The factorial and the little lisper  .  In that case, I was able to produce a working example, and as well some funny ones, like this version of the factorial of 5:

 

(taken from the Chemlambda for the people html/js slides)

This happens because there is a mix between execution and duplication which sometimes goes astray. For example if I take the molecule goi-2.mol

FO out out1 out2
A 1 2 out
A 3 4 1
L 5 f 3
FO f 7 9
A 7 8 6
A 9 x 8
L 6 x 5
A 10 11 4
L y y 10
L z z 11
L w w 2

which is exactly like the molecule goi.mol for the lambda term A (seen in the previous post), only with

FO out out1 out2

added, then the execution (reduction) of the two copies of A while they duplicate, it goes great:

 

That is because the nodes FO, FOE and FI satisfy the shuffle trick, which guarantees the duplication of FO trees from lambda terms molecules (in particular).

I suspect that there is a choice of the FO fanout trees in the conversion of a lambda term into a molecule which does the job.

Don’t know how to prove it 🙂

 

Diagrammatic execution models (Lambda World Cadiz 2018) compared with chemlambda

Via this MonkeyPatchBlog post I learned about a keynote presented at the Lambda World Cadiz 2018, on Diagrammatic execution models, quote:

” Koko Muroya and Steven Cheung, working under the direction of Dan Ghica, gave a fantastic overview of their work on diagrammatic execution model.   […]

There is a nice demo of their work hosted on github, which was used during the presentation. […]

Applied category theory is booming right now, and this work led me to wonder if they were considering describing their work in a categoretic way (yes, it seems). Some of the demos they showed were reminiscent of chemlambda: a graph evolving given rewriting rules (which incidently provided the illustration for the ACT 2019 announcement).”

So I wanted to see how does the lambda term reduce in chemlambda (with the random reduction).

Here is the GoI Visualiser in action: the term is ((λf. λx. f (f x)) ((λy. y) (λz. z))) (λw. w)

reduced with call-by-need looks like this:

Comparison with chemlambda. The mol file goi.mol for this lambda term is:

A 1 2 out

A 3 4  1

L 5 f 3

FO f 7 9

A 7 8 6

A 9 x 8

L 6 x 5

A 10 11 4

L y y 10

L z z 11

L w w 2

I prepared an archive with all needed, taken from the chemlambda repository. You may just download it and then you shall see in the mol folder the goi.mol file. To produce (a) reduction you write in terminal

bash quiner_shuffle.sh

then you write

goi.mol

then you see that a file goi.html appeared. You write

firefox goi.html &

and you see this:

 

or something equivalent. So that’s how the reduction of this term looks in chemlambda. 🙂 Well, the animated gif shows that again and again…

UPDATE: Thank you for the interest and nice words. If you don’t like my way of writing code, which is to be expected because geometer here, then there is this Haskell implementation.

My opinion is still that the most interesting ideas of chemlambda are:

• that “real molecules which embed Interaction Nets patterns and real chemical reactions which resemble Interaction Nets graph rewrites could be a realistic path towards molecular computers“
• that differential calculus in spaces more general than riemannian can be put into a graphic formalism, very close to chemlambda, see for example the last  arXiv:1807.02058.

As concerns the first point, this justifies the accent on the dumbest, random, local reduction algorithm, and the experiments outside graphs which represent lambda terms (from all those chemlambda quines to mixtures of busy beavers and lambda terms).

As for the second point, there is really a lot of mathematics, perhaps logic too, to be explored here.

 

 

 

 

Chemlambda collection afterlife [updated]

Still, hundreds of posts available via reshares from the chemlambda collection. Recall that I deleted the collection some time ago, see here.

I arrived at the conclusion that there is no reason to hide recent or (sometimes) older research from public, just because I believe the academic publishing is close to collapse.

So I started by posting on arXiv a text version of the experimental article Molecular computers, available now as arXiv:1811.04960.  The JS animations are replaced with links and there is a note to the reader added.

The same article is also posted at Figshare:

https://doi.org/10.6084/m9.figshare.7339103.v1