Tag Archives: universality

A project in chemical computing and Lafont universality

The post Universality of interaction combinators and chemical reactions ends with the idea that Lafont universality notion, for interaction systems, may be the right one for chemical computing.

These days are strange, every one comes with some call from one of my old projects. (About new ones soon, I have so many things.) Today is even more special because there were two such calls.One of them was from what I wrote in A project in chemical computing page from april 2015. It ends with:

    If you examine what happens in this chemical computation, then you realise that it is in fact a means towards self-building of chemical or geometrical structure at the molecular level. The chemlambda computations are not done by numbers, or bits, but by structure processing. Or this structure processing is the real goal!
     Universal structure processing!

There is even this video about an Ackermann function molecular computer I forgot about.

The idea is that the creation of a real molecule to compute Ackermann(2,2) would be the coolest thing ever made in chemical computing. If that is possible then as possible as well would be an Ackermann goo made from Ackermann(4,4):


In Graphic lambda calculus and chemlambda (III) I comment again on Lafont:

    • Lafont universality property of interaction combinators means, in this pseudo-chemical sense, that

the equivalent molecular computer based on interaction combinators reactions (though not the translations) works

    for implementing a big enough class of reactions which are Turing universal in particular (Lafont  shows concretely that he can implement Turing machines).


In the series about Lafont interaction combinators and chemlambda (1) (2) (3), as well as in the paper version of the article Molecular computers, an effort is made to reconnect chemlambda research with much older work by Lafont. [UPDATE: I retrieved this, I forgot about it, it’s mostly chemlambda v1¬† to chemlambda v2, see also this post ]

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.