Universality of interaction combinators and chemical reactions

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

lafont-1

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:

lafont-2

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:

chi-kai-s-min

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.