Tag Archives: chemical abstract machine

An apology of molecular computers and answers to critics

This is how a molecular computer would look like, if seen with a magically powerful microscope. It is a single molecule which interacts randomly with other molecules, called “enzymes”, invisible in this animation.


There is no control over the order of the chemical reactions. This is the idea, to compute without control.

The way it works is like this: whenever a reaction happens, this creates the conditions for the next reaction to happen.

There is no need to use a supercomputer to model such a molecule, nor is it reasonable to try, because of big number of the atoms.

It is enough instead to find real molecular assemblies for nodes, ports and bonds, figured here by colored circles and lines.

The only computations needed are those for simulating the family of rewrites – chemical reactions. Every such rewrite involves up to 4 nodes, therefore the computational task is handy.

Verify once that the rewrites are well done, independently of the situation where you want to apply them, that is all.

Once such molecular compounds are found, the next task is to figure out how to build (by chemical reactions) such molecules.

But once one succeeds to build one molecule, the rest is left to Nature way of computing: random, local, asynchronous.

From this stage there is no need to simulate huge molecules in order to know they work. That is something given by the chemlambda formalism.

It is so simple: translate the rewrites into real chemistry, they are easy, then let go the unneeded control from that point on.

This animation is a screencast of a part of the article Molecular computers
and everything can be validated (i.e. verified by your own) by using the chemlambda repository

Now I’ll pass to a list of critics which, faced with the evidence, they look uninformed:
1. Chemlambda is one of those rewriting systems everybody knows. Ignorant claim, while it is true that some rewrites appear all over the place, from string theory to knot theory to category theory to geometry of interaction, the family of graphs considered is not the same, because those graphs are purely combinatorial object and they don’t need a global embedding, like all other formalism do, in a schematic space-time. Moreover, the choice of the rewrites is such that the system works only by local rewriting and no global control on the cascade of rewrites. No other formalism from the family does that.

2.  Is well known that all this is already done in the category theory treatment of lambda calculus.

False, if one really reads what they do in category theory with lambda calculus, then one figures quick that they can’t do much for untyped lambda beta calculus, that is without eta reduction. This is mentioned explicitly in Barendregt, for example, but the hype around categories and lambda calculus is so pervasive that people believe more than what actually is.

3.  Chemical computing is old stuff: DNA computing, membrane computing, the chemical abstract machine, algorithmic chemistry.

Just because it is chemical computing, it does not mean that it is in the family mentioned.

The first name of chemlambda was “chemical concrete machine” and there there are comparison with the chemical abstract machine
(btw I see that some people discover now “catalysts” without credits in the written papers)
The cham is a formalism working with multisets of molecules, not with individual ones, and the computation is done by what corresponds to lab operation (splitting a solution in two, heating, cooling, etc)
The membrane computing work is done around membranes which enclose containers of multisets of molecules, the membrane themselves being some abstract concepts, of a global nature, whil ein reality, as well as in chemlambda, everything is a molecule. Membranes exist in reality but they are made of many molecular compounds.
DNA computing is an amazing research subject, which may be related to chemlambda if there is a realization of chemlambda nodes, ports and bonds, but not otherwise, because there is not, up to my knowledge, any model in DNA computing with the properties: individual molecules, random reactions, not lab operations.
Algorithmic chemistry is indeed very much related to chemlambda, by the fact that it proposes a chemical view on lambda calculus. But from this great insight, the paths are very different. In algorithmic chemistry the application operation from lambda calculus represents a chemical reaction and the lambda abstraction signals a reactive site. In chemlambda the application and lambda abstraction corresponds to atoms of molecules. Besides, chemlambda is not restricted to lambda calculus, only some of the chemlambda molecules can be put in relation with lambda terms, but even for those, the reactions they enter don’t guarantee that the result is a molecule for a lambda term.

Conclusion: if you are a chemist, consider chemlambda, there is nothing like it already proposed. The new idea is to let control go and instead chain the randomly appearing reactions by their spatial patterns, not by lab operations, nor by impossibly sophisticated simulations.
Even if in reality there would be more constraints (coming from the real spatial shapes of the molecules constructed from these fundamental bricks) this would only influence the weights of the random encounters with the enzymes, thus not modifying the basic formalism.
And if it works in reality, even for only situations where there are cascades of tens of reactions, not hundreds or thousands, even that would be a tremendous advance in chemical computing, when compared with the old idea of copying boolean gates and silicon computers circuits.


Appeared also in the chemlambda collection microblog



Fraglets, bionets, and the www with metabolism

In the post  WWW with Metabolism  and  The chemical connectome of the internet  was evoked the idea of using the chemical concrete machine not on biological, wet networks (although I still find this line of research very promising), but on the www. I am very happy to see that efforts concerning the use of chemical programming and bio inspired models of programming already exist!

Tell me more about this, if you read this and you are an expert! (And, of course, excuse my ignorance, I am a geometer, not a CS expert, therefore I shall mention your previous work here, as I learn about it.)

Fraglets is an extremely promising direction: here is the  fraglets site and here is a fascinating article by Christian F. Tschudin. The title of the article is  “Fraglets – a Metabolistic Execution Model for Communication Protocols”  and the abstract reads:

In this paper we introduce a molecular biology inspired execution model for computer communications. The goal is to lay the ground for automatic network adaption and optimization processes as well as the synthesis and evolution of protocol implementations. Our execution model is based on the unification of code and data, featuring a single unit called “fraglets ” that are operands as well as operators. We have built a simulator and started to program classical communication tasks with fraglets that show metabolistic pathways patterns like the ones found in biological cells. We give an example of a fraglet implementation for a non-trivial flow–control–with–reordering protocol and briefly discuss how to search the fraglet program space with genetic algorithms.

I like very much two things here: “unification of code and data” and the “metabolistic” word in the title.

Lidia Yamamoto is another researcher who works in the (finished?) BIONETS collaboration, with Biochemically inspired emergent computation,  co-authored with Thomas Meyer. Also, with Christian Tschudin,  “A metabolic approach to protocol resilience” (here, from p. 191).

Of course, Banatre is the first who introduced the concept of “chemical programming” and Berry with Boudol the CHAM, or the chemical abstract machine. (Recall that the “chemical concrete machine” denomination points to the CHAM, but it is “concrete” because really it works with “concrete” molecules, involved in “concrete” chemical reactions, without using any name (or name management), and without the need for evaluation in the computation).

Why build a chemical concrete machine, and how?

Asked about this, I spent a bit thinking and I arrived at  this very brute answer:

What I have in mind can be split in two.

There is a first part concerning graphic lambda calculus seen as it’s about real molecules interacting in space. For this part I would like to construct graphs which are like a Turing machine (or other computing devices) then, the important step is to eliminate everything which is due to our human 1d writing conventions (see details in the rant from the first part of this post) and thinking and simplify such “machines”, in the same way, for example, like I saw it’s possible

A serious tool for doing this would be, for example, a program which allows to visualize and perform moves  (automatically and from the keyboard) on graphs in GRAPH.

The second part, which goes in parallel, would be to try to find in the real world (here DNA origami looks like a possible tool) ways to construct chemically, physically, such machines, which are naturally adapted to the real world because they are geometrical (an object or a property is geometrical if it can be described, or it’s invariant to an arbitrary change of parametrization, in our case, an arbitrary renaming).  For this part I want to understand first how DNA origami works, to the level of being able to absorb information and understand some of the hurdles.  This leads to applications, which are still vague in my head, but I was impressed by this video

as well as by research of Jean-Pierre Banatre and Daniel Le Metayer.

In conclusion, I can’t imagine what a syringe with 10^9 nano geometrical turing machines  graphs representing lambda terms [see UPDATE]  can’t do.


UPDATE:  Corrections to this post are made in  Chemical concrete machine not algorithmic self-assembly of DNA, nor Turing machine   , where it is stressed that the “chemical concrete machine”, even if it has Turing universality property, it is not intended to be a Turing machine, (nor an automaton), as is wrongly suggested in this post.

A chemical concrete machine for lambda calculus

This post is a call for building one. More precisely, for building one for graphic lambda calculus, which satisfies all the requests  from section 5 of The chemical abstract machine by Berry and Boudol  for a calculus more general than lambda calculus.

First a short comment on “The chemical abstract machine”. This is a very interesting article, thanks are due  to Mike Stay for telling me about it, in relation to what is described in my previous post  Can graphic lambda calculus be implemented in some form of DNA computing?  The following quote describes exactly what I was looking for (p.1 from the linked file):

Intuitively, the state of a system is like a chemical solution in which floating molecules can interact with each other according to reaction rules … Solutions are finite multisets of molecules …

But from here I will not jump to identify terms in lambda calculus with solutions, like it’s done in section 5.2 on the \gamma calculus. Nor shall I use membranes and airlocks, as useful as they seem (and probably there is a possible implementation of those in graphic lambda calculus).

Finally, there is something which I don’t understand in the article, concerning variables and substitutions. I might be wrong, please tell if so, but apparently an abstract chemical machine still uses names for variables, which appear as “ions”. What I don’t get is: how are two solutions, each one corresponding to a lambda term, the same if the two lambda terms are the same by renaming the variables?

In graphic lambda calculus there is no such problem, because there are no variable names. Moreover, lambda terms (which appear as certain graphs in graphic lambda calculus) are molecules and the moves between them (like the graphic beta move) are chemical reactions.

How can this be done? Here is sketch, mind you that I propose things which I believe are possible from a chemical perspective, but I don’t have any chemistry knowledge.  If you do, and if you are interested to make a chemical concrete machine for graphic lambda calculus, then please contact me.

The graphs from GRAPH which we need for the lambda calculus sector of the graphic lambda calculus, are  made by three gates corresponding to lambda abstraction, application and fan-out (I shall ignore the termination gate). So we need three molecules.


The five coloured triangles are parts of the molecules which bond one with the other. Say there is a bond strength associated with each pairing, such that the bigger is the bond strength, more easily the bond is made and more stronger it is.

Remark that the molecules from the right of the figure don’t seem to have oriented arrows inside. That is why we need several types of bonding places. The table of bond strengths is this:


The strength coefficients are taken out of … my imagination, such that they satisfy a number of mental experiments I did with them.  As you see there are:

  • two bonding places — yellow and red, which correspond to input half-arrows,
  • two bonding places — blue and green, which correspond to output half-arrows,
  • one bonding place – magenta, which can be seen as well as input or output half-arrow.

The bipartite graph from the lower part of the figure shows which bonding places CAN bond (i.e. they have bonding strength not equal to 0).  In the upper part of the figure there is a table with strengths.

As you see, this solves the problem of representing decorated nodes of oriented graphs. Nice.

Now, let’s pass to the main move, the graphic beta move. This should be a chemical reaction. Imagine that we have an enzyme called “beta”, which recognizes magenta-magenta bonds. When it does recognize such a bond, it does like in the next figure:


So, the beta enzyme cuts the other bonds, like in the middle part of the picture, then the bonding places bond according to the strength table. Voila!

If you want to play with, here is a “chemical” representation of the 2-zipper, try to see how it works.


I hope this adds more details to my call of building a real, concrete chemical machine (or to recognize one with at least the expressivity of untyped lambda calculus). Can anybody do it?