How to simulate an enzyme with a quine in chemlambda (I)

I discussed many times here about the view which has chemlambda about graph rewrites as invisible enzymes. Here is, I believe, the first picture describing this idea for the beta move (taken from this post)

enzyme_2Since that first proposal the formalism changed, see this page which collects the updates, explanations and some useful links. However I shall lay down soon a detailed tutorial on the actual state of chemlambda.

Further I want to explain how we can make “move enzymes” visible in chemlambda. For this I shall use chemlambda quines and a kin dof bootstrapping, along with a new primitive construct, which appeared already several times before, denoted by “:”, wait a minute and let me take the ingredients one by one.

1. I start by stating again a very simple fact about what is chemlambda (and what is not). Chemlambda is a graph rewrite system which uses an analogy with chemistry. The graphs are called “molecules” and the graph rewrites are seen as chemical reations with invisible “move enzymes”. That’s about how far the analogy goes. It is not a part of the analogy the use of other concepts, as for example chemical reaction networks, Petri nets, probabilities, etc, because these are only external ingredients (or modules, or layers) which can be added over chemlambda in order to obtain a model of computation. Moreover, they are not, by far, the most interesting modules to add.

So, chemlambda is just that: a graph rewrite system. It is comparable with the Alchemy of Fontana and Buss, in the following precise sense: lambda calculus terms and reductions can be simulated by chemical molecules and reactions. But it is very different  Alchemy (and also from the CHAM of Berry and Boudol) because in chemlambda the abstraction and the application appear as nodes in the graph-molecules, while in the Alchemy the application and abstraction have different statuses.

2. If you want to get a model of computation from chemlambda then you have to add new ingredients. My ultimate goal is a model of asynchronous, distributed, decentralized model of computation, sketched already in the article M. Buliga, L.H. Kauffman, GLC actors, artificial chemical connectomes, topological issues and knots, arXiv:1312.4333 , as well as in many posts here, in the category distributed GLC.

But say that there is a lot of programming work to do, therefore it may be a good idea to take it slower and explore as many possible simpler models of computation based on chemlambda.

The first such model is one which is sequential, using the mol files convention, quickly described by the following:

  • if no LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR are present in the g-pattern, then stop, else
  • identify the LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
  • apply the moves from LEFT to RIGHT
  • apply the COMB moves until no Arrow element
    can be eliminated
  • repeat.

This is the model implemented in the scripts from the chemlambda gui repo, see for the mol files convention this crude intro.

This makes a model of computation which is already very interesting. I just mention as examples the Ackermann function computation , and a no nonsense clarification of the mechanism behind the Y combinator: the Y combinator is just a gun shooting pairs of applciation and fanout nodes, the recursion is in fact done by self-multiplication of the molecules. The significant fact is that (some) molecules can self-multiply without any external management, only by the local graph rewrites, in this model of computation.

On the open questions side, concerning this model of computation, the most interesting seems to be: what kind of computation is this? Is it functional programming (just because it can do, but is not limited to lambda calculus)? [It appears that not, despite superficial resemblances, because it can do untyped lambda beta — and not eta — calculus, therefore there is no notion of a function in chemlambda] If not, what is it? Maybe the reduction strategy helps to classify it in one of the big categories. But the reduction strategy does not use any evaluation step. More concretely, for some particular examples of reductions of molecules which represent lambda terms (I choose this molecules in order to have a common ground for making comparisons, not because of a limitation of chemlambda to lambda calculus only), the reduction process resembles with one based on call-by-need evaluation, other times not, see this post for some details.

All this — self-multiplication instead of recursion, reduction by something akin to signal transduction — make already this simplest model of computation curiously alive. Alife.

3. Still in this simple model of computation there are some molecules, called chemlambda quines, which have the property that even if the reduction process goes forever, at each step the molecule is globally the same. (Some of) these quines are derived from molecules called walkers. A walker is a molecule which stays the same in a bigger one (imagine a walker on the road; even if the walker advances, by translation symmetry the road-and-walked ensemble stays the same). You just take a walker on a closed road and you get a quine, for example.

What is nice about quines is that they respect the analogy with chemical molecules-chemical reactions in the following sense. During the reduction process (chemical reaction) the number of atoms (nodes) is conserved.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s