Tag Archives: chemlambda

Chemical concrete machine, detailed (II)

Continues from the  Chemical concrete machine, detailed (I).  In this part I connect with  the previous post  Chemical concrete machine, short list of gates and moves, then there is a discussion part.

__________________

Let’s look again at the two examples of chemical reactions from the first part:

ess_4

These reactions look as being complementary, as if one is the inverse of another. Indeed, this is the case, but for seeing this better we need to refine a bit the notations.

For each reaction is specified an enzyme, \beta^{+} for the first reaction and \beta^{-} for the second reaction, and moreover a reaction site, denoted by closed red, dashed, curve. The meaning is that the enzyme react with the molecule by binding at the reaction site and by modifying it, without any other action on the rest of the molecule.

Practically, each enzyme changes a small preferred pattern into another. The rest of the molecule does not take part to the reaction and for this reason is better to concentrate exclusively on the reaction sites and how they change.

The next figure represents this change, for the pair of complementary enzymes \beta^{+} and \beta^{-}.

ess_5

(The crossing from the right hand side of the figure is not real, remember that the molecules float in a 3D container. The 2D drawings we make are projections in the plane of what we see in space.)

The drawing is made such that to make clear the correspondence between  the free ends or beginnings of arrows pointing or coming from the rest of the space.

Now is clear why the two reactions are one the inverse of another. Finally, we represent both reactions like this:

ess_6

In graphic lambda calculus, this is the most important move, namely the graphic beta move. It corresponds to the beta reduction from lambda calculus.

As simple as it might seem to the eyes of a biochemist, it has tremendous powers. Besides (graphic lambda calculus), it appears also in topology research related to various theories in quantum physics, see the UNZIP move described in   The algebra of knotted trivalent graphs and Turaev’s shadow world  .

__________________

I can now describe the allowed chemical reactions with enzymes in the model of the chemical concrete machine. I reproduce further the last figure from the post Chemical concrete machine, short list of gates and moves , with the understanding that it describes such chemical reactions, with the notational conventions detailed here.

Reactions with enzymes are called “moves”, as in graphic lambda calculus. Moreover, for each reaction-move is given a link to the description of the said move in graphic lambda calculus.

convention_2

convention_3

convention_6

convention_4

The last move, elimination of loops,

convention_5

is not a chemical reaction, however! It’s meaning is that loops can be considered garbage (element of GARB). This is in contradiction with the assumption that GARB consists of reaction products which don’t react further with the molecules. Sometimes we might need reactions between loops and enzymes, like \beta^{-}.   This is a subject which will be discussed later, but the zest of it is that GARB may also be seen as the collection of reaction products which we don’t want to detect at the end of the chain of reactions.

The list of allowed chemical reactions is minimal. We may add other reactions, like reactions between the “other molecules”, this will also be discussed later.

I the next post I shall describe what the chemical machine can do, in principle.

__________________

Discussion.    We have now at our disposal an universe of molecules and a family of allowed chemical reactions. In order to get a usable model we need a bit more. The natural addition would be to put these reaction in the form of a chemical reactions network, or, equivalently,  a Petri net. This is a path to follow, which will give explicit, numerical, predictions about the behaviour of the chemical concrete machine.

We cannot apply directly Petri nets to the situation at hand, because the chemical reactions, as described here, are between reaction sites, and not between molecules. A molecule may have several reaction sites, moreover there are reaction sites which involve two molecules. After each possible reaction with an enzyme, the resulted molecule, or molecules, may have several reaction sites as well.

Moreover, a reaction site, say, which involves two molecules, like the reaction site containing two arrows, possibly from different molecules, are aplenty. We need to make physical assumptions like saying that a reaction site might be localized in the 3D space, otherwise we have a combinatorial explosion of possible reactions involving one, or a pair of molecules.

These problems related to reaction sites have surely been studied elsewhere. One possible place to learn from might be (in the view of a naive mathematician like me), the research around the  SCHEMA algorithm.   Are reaction sites schemas?

This brings us to the question of the real implementation of the chemical concrete machine. It is clear that the subject belongs to the synthetic biology field and that there is a strong need for a collaborative help from specialists in this field.

There are two possible ways for such an implementation:

  • to construct molecules like the essential ones, with the purpose of manipulating interesting other molecules, which appear in the model as the “other molecules”. Indeed, as we shall see, the chemical concrete machine can perform logical computation (it is Turing complete) in a much simpler form than imitating the structure of a silicon computer (instead, it uses extreme functional programming), and also it can perform geometrical operations, like hoarding and grouping interesting “other” molecules, releasing them at the detection of a chemical signal, and so on, again in a much simpler way than by imitating a mechanical large scale machine, or a silicon computer with actuators and effectors.
  • or to recognize chemical reactions in the reality, for example in a living organism, which satisfy the chemical concrete machine formalism. In this second case, which might be likely due to the simplicity of the formalism, the information we get from the chemical concrete machine model is semantic, eg. if we want to “convince”  a living cell to do a certain logical computation, we may exploit the chemical concrete machine formalism, embodied in the cell by recognizing the reactions which are meaningful for the formalism, and then trying to find out how to exploit them (basically how to detect or amplify their effects). This second way seems to be related to the extremely interesting path opened by Fontana and Buss , saying that essentially lambda calculus is something a sufficiently complex chemical reaction  network manifests.

Chemical concrete machine, detailed (I)

This is the first in a series of posts which have the purpose to explain in detail the chemical concrete machine. Please read the previous posts with the tag chemical concrete machine and also consult the tutorial on graphic lambda calculus, if needed.

As a motivation, see  Extreme functional programming done with biological computers.

_____________________

I look forward for comments, corrections and contributions.

_____________________

In the following I shall use the name “molecule” in a very loose sense. A molecule is seen as made by other smaller molecules (for example atoms are molecules) which are connected by chemical bonds, or by other molecules called “arrows”. Therefore, a molecule is seen as a graph with nodes which are smaller molecules and arrows which connect those nodes.

There might exist molecules with free arrows, or bonds.

Besides molecules, I shall also use “enzymes”. A chemical reaction will always involve two molecules, or a molecule and an enzyme.  The product of the reaction is a molecule plus garbage, denoted “GARB”, which can be a collection of molecules which are inactive (i.e. they cannot be part of any other chemical reaction).

We shall work with a list A, B, C, ... of unspecified molecules, which can react (or not) one with another, this is left to the choice of the user of the chemical concrete machine. Besides this bag of names of molecules, we have a short list of essential molecules, which are the ingredients of the machine.

For convenience, arrows and loops (i.e. closed arrows) are seen as molecules.

All this is described in the following figure.

ess_1

On the first row you see the list of essential molecules, named respectively

  • “app”, corresponding to the application gate in (graphic) lambda calculus
  • “y”  ,  corresponding to the FAN-OUT gate in graphic lambda calculus
  • “lambda”, corresponding to the lambda abstraction gate in (graphic) lambda calculus
  • “f” , corresponding to the \varepsilon gate in graphic lambda calculus

For the moment these correspondences don’t mean much, therefore I leave the explanation for later. There are four essential molecules, called app, y, lambda and f.

On the second row we see a loop, an arrow (which are considered molecules, as written before), and a molecule called “term”, which corresponds in graphic lambda calculus to the termination gate.

In the last part of the figure you see the list of enzymes. What is to be noticed is that any enzyme comes in two flavors: “+” and “-“. The reason for this is the following. Any chemical reaction which involves a molecule and an enzyme will correspond to a move in the list of moves of the chemical concrete machine  . If you examine these moves then you shall notice that they go in both directions. Therefore, such a move appears as a pair of unidirectional moves. By convention, the moves from left to right are denoted by “+” and the moves from right to left are denoted by “-“. To each such move is associated an enzyme.

_____________________

With molecules and essential molecules we build larger molecules. The physical, concrete way of constructing such molecules is left unspecified (although it can be done in the formalism of the chemical concrete machine).  Here are some examples of larger molecules.

ess_2

We imagine that all molecules float inside a 3D container. There may be several copies of the same molecule in the container.

Generally, the rule of building molecules is that they are made by other molecules and essential ones, simply by connecting the arrows and respecting the arrows orientations. More technically, with the correspondences specified previously, the rules of building molecules are exactly the ones for building graphs in the set GRAPH described in the post Introduction to graphic lambda calculus. The only new thing is that we admit also a list A, B, C, ... of unspecified nodes with unspecified valences, which model “other molecules”.

_____________________

So, in this simplified view of reality, molecules are such graphs. Let us see how they react with enzymes. We cannot simply write reactions as

molecules + enzyme = molecules + GARB

because these molecules may be complicated beasts (graphs) and because, as we shall see, the enzymes prefer to react with certain patterns (subgraphs) of molecules. For specifying how the reaction takes place we need:

  • molecules
  • an enzyme
  • and a “reaction site”, which is a small part of the initial collection of  molecules.

The reaction site have to be present in the molecule, otherwise the reaction cannot happen.

In the following figure I consider two examples of reactions (which correspond to graphic beta moves in the realm of graphic lambda calculus).

ess_3

In the first row we see a reaction between a molecule and the enzyme \beta^{+}, which results into two other molecules and some GARB.  There is a small region in the initial molecule, marked by a dashed red closed curve, which represents a reaction site for the \beta^{+} molecule.

In the second row is written the same reaction, but in a simpler form. The red “+” sign is eliminated, the two molecules which are obtained are juxtaposes, as if they are floating in the 3D container, and the GARB is ignored. Moreover, the enzyme \beta^{+} points towards the reaction site.

The rows 3 and 4 describe another reaction. At closer inspection, it’s a reaction which can be interpreted as the inverse of the first one.  Let’s examine directly the 4th row (which is obtained from the 3rd row  by the same procedure as the 2nd row was obtained from the 1st).  The reaction site of the enzyme \beta^{-} is a pair of arrows from two different molecules, The resulting molecule is the same as the initial molecule from the previous reaction.

_____________________

In the next post I shall continue with the chemical reactions which are allowed, with all details.

Extreme functional programming done with biological computers

After a very interesting hangout with Eugenio Battaglia and Gerd Moe-Behrens emerged this idea: to use the functional programming for biological computing. It is not straightforward to explain it, therefore I use this post in order to clarify a bit what is my understanding of the problem.

As a background for this description, consider that I am a mathematician, which is a mixed blessing, because even if some ideas seem easy in mathematical terms, they turn out to be hard to explain without explicit recourse to mathematics. On the other side, I am ignorant concerning chemistry and biology, therefore handicapped in discussions with specialists outside my narrow mathematical world.

Further I shall describe things from my point of view, within the mentioned constraints which shape my understanding. I am not sure if I gave the right description of the zest of the discussion.

1. Apparently, as Gerd Moe-Behrens explains in The biological microprocessor, or how to build a computer with biological parts, there is a trend to use the architecture of a silicon computer for building a biological computer. In particular this means to try to build boolean logic gates,  or memory.  It is an important observation that whatever happens in a living cell which resembles to computation (in a more vague sense than Turing computation) is not necessarily implemented as in a silicon computer. Instead, synthetic biology tries to import concepts from silicon computers into the bio realm, mainly because these concepts are already familiar. Hence the accent on bits and boolean logic, although not exclusive (other studies concern for example membrane computing, or neural networks, or continuously evolving dynamical systems).

2. On the other side, functional programming  is one of the main  programming paradigms, a very elegant one,  receiving more and more attention in the competition with the more well known imperative programming . Or, evaluation of boolean circuits, which is taken as a role model in many studies of biological computing, is more natural in the imperative programming paradigm. However, functional programming has its roots in the lambda calculus, one of the two pillars of computation, along with the Turing machine (of equivalent power, but with different philosophies behind).

3. In 1994, Fontana and Buss, in a pair of articles, introduce the idea that lambda calculus is a kind of natural formalization of the bare bones of  chemistry.  Molecules are seen as lambda terms, collision of molecules is seen as the application operation in lambda calculus, and  the abstraction operation from lambda calculus “captures the role of functional groups embedded in the reactants” [source, p. 11].

4. By the previous points, it is only natural to try to use the functional programming paradigm for biological computing. This means in particular to no longer chase for logical gates and boolean circuits.

5. An interesting thing is to notice that Fontana and Buss use lambda calculus with eta reduction, i.e. the terms (or molecules) are identified with functions, in the sense that the molecule A is identified with the function B \mapsto AB. Also functional programming, as far as I understand, also use this eta reduction, being more interested into types.

6. Independently, I built graphic lambda calculus, which is even more powerful than  lambda calculus. One of the interesting parts of graphic lambda calculus is that it makes clear that the beta reduction (which is the main reduction move in lambda calculus) is local in nature (read “simple to implement in reality”) and the eta reduction, as innocuous as it might look to our powerful brains, is in fact a global reduction move (here you see the eta reduction in graphic lambda calculus).  Therefore, I believe that “extreme” functional programming (i.e. without extensionality) is more likely to be implemented in reality (i.e. outside a silicon computer).

7. In graphic lambda calculus we work with graphs, (some of them) corresponding to lambda terms. We could identify them with chemical molecules, as it’s done in algorithmic chemistry.  But there are some differences between algorithmic chemistry and my chemical concrete machine proposal, namely that  the application and the abstraction operations from lambda calculus are, in the concrete machine, ingredients of molecules, and moves (reductions) are assimilated with enzymes, thus reductions are certain chemical reactions.

8. This leads us to the last point: it is intriguing to search if “extreme” functional programming (i.e. functional programming without extensionality) could be implemented in biological computing. The advantage of this extreme functional programming paradigm is that it might be much more simple to do this implementation than to mimic a silicon computer, because already lambda calculus looks like a kind of chemistry. Another advantage, coming from the fact that the chemical concrete machine uses the graphic lambda calculus formalism, is that geometric operations (like bonding two molecules together, or performing reduction steps in parallel)  are more simple to describe in graphic lambda calculus than in the usual lambda calculus.

The disadvantage is that is hard to understand lambda calculus without extensionality. It is already hard to understand functional programming, by someone with the imperative programming mindframe. Without extensionality, is then even harder to not fall into habits of thinking which might be misleading. I know this, because two years ago all this lambda calculus was totally opaque to me. Why, not using equality? Not using functions? Is this mathematics or some crazy invention of logicians? Now I know better, of course. But for somebody which is used with boolean logic and (like me) with functional analysis, it looks crazy first.  If you go further, then you start to love it.

Algorithmic chemistry and the chemical concrete machine

I just discovered the work of Fontana and Buss on Algorithmic Chemistry. The ideas appear to be very close to what I am trying to do with the chemical concrete machine (independently, because of my relative ignorance of past research in the field, but I’m improving my knowledge day by day).

I shall jump directly to differences. At first sight there are a lot of ideas which look the same, mainly that lambda terms are molecules and chemical reactions are related to reduction in lambda calculus.

The main differences are:

  • for the chemical concrete machine, molecules are not just any abstract list, but a particular one, expressed as certain graphs,
  • I don’t use lambda calculus, but a more powerful version, graphic lambda calculus, which works directly with such “molecules” (i.e. graphs in GRAPH), being free from any linear writing convention or variable names,
  • chemical reactions between such molecules do not correspond to lambda abstraction or to the application. Instead, the chemical reactions correspond to reduction moves, mainly to the graphic beta move,
  • molecules are not functions, because of the lack of extensionality (eta reduction), which is good, because it makes the calculus much more concrete than with extensionality (but this is an argument which needs more details, that’s for later). For now I shall just mention my belief that extensionality and types are an unnecessary relics of thought (controversial, I know) and one of the main stumbling blocks on the path of reconciling syntactic with semantic is keeping types and extensionality (the short argument against these is that there’s nothing like types or extensionality  in any biological brain, and probably is just another manifestation of the cartesian disease).

But otherwise my proposal of the chemical concrete machine is clearly in the field of algorithmic chemistry!

Message in a bottle

I don’t know how you function, but I use to send messages, containing ideas which turn around in my head, to whom I think might be interested, as an invitation to dialogue, or as a request for help.

Reading such messages afterwards, almost always I notice that it is not obvious what are my intentions and motivations, even to me.

Nevertheless, on a longer time scale, these become transparent. Some look a bit like messages in a bottle which I send from a remote island and years after I receive them on another shore.

These poetic lines, partially motivated by the sun intake and the proximity of the sea, are an introduction to such a bottled message, which I just received and moreover one which can be used as evidence for the long time scale phenomenon.

I use now an older laptop, the one which I had with me when I was in Rio. I don’t know if I wrote this before, or if anybody cares (but indulge me to use this place as a log, besides being an open notebook), the strongest feeling I had back in Rio was one of total freedom. And what does a free mathematician these days? Well, I decided I would like to switch to biology, of course.

I have a folder on my laptop, created in Rio, called “next”. What’s that? I asked myself today and opened it. Inside there’s a latex file “bio_next”. Aha, let’s see, I don’t remember what ‘s  about.

In the file is a collection of quotes from messages sent to somebody I shall not mention, because they are part of strange messages which probably did not have any meaning from the receiver point of view.

But I invite you to compare these messages with the content of the chorasimilarity open notebook, in order to prove that there’s a long time scale coherence. Hopefully, now I am a bit wiser and I keep a log.

I shall mention also, because as somebody said that the net is not subtle, that the purpose of sharing these messages is to invite you, dear reader, to dialogue.

Here is the content of the file (latex commands and names/places  excluded):

nov 14 2007:   I hope to be in ..  at the beginning of December (but  not 100 percents  sure). I could pass by … if you are there,  because I am very curious about your opinion. Mine is  that even these contributions are unworthy, they show  the existence of an infinite field of analysis. So maybe  this could nuance the old dichotomy discrete-continuum a  bit.

feb 1, 2008:      On another note, I am (was) impressed by your turning to biology and  now am part of a project in molecular dynamics (more of less). So  now I am strugling with questions like: what are “shape” and  “function” meaning for a biochemist? Very non bourbakian notions.

oct 5, 2009:  I think that the paper is difficult for someone not in the right frame of mind and rigid. I also believe that it is important, less because it gives a kind of axiomatization of SR geometry, but more because it shows  that there is a world of analysis outside  the regular paths. And I think is relevant for understanding our presupositions concerning the space, but I noticed that this is not a viewpoint to discuss in a math paper for publication.

nov 16, 2009:   Question (to your curiosity): if a squirrel  (monocular vision times two eyes) would do analysis,  what it would look like?  My tentative answer: the axiom A4 (with the approximate  difference operator, the one from the last section  of Bellaiche SR paper) of dilatation structures, seems  natural to us,  binocular vision beings. To a squirrel,  the most natural is to base everything on the  approximate inverse operator ( inv , see the previous  “Emergent algebras as generalizations of differentiable   algebras, with applications” http://arxiv.org/abs/0907.1520  )   Therefore,  a squirrel would start to do analysis on  symmetric spaces, not on vector spaces as us.

jan 5, 2010:    Question: The basic component of dilatation structures (and therefore  of any scheme, let’s say, of finite differences) are dilatations. A  dilatation is just a gate with two entries and one output. The calculus  with dilatations consists in finding interesting binary trees with  nodes beind dilatations, such that when \varepsilon goes to 0, the output  of the tree converges.  Likewise, boolean calculus is based on the transistor (say, a NAND  gate) and any circuit made by transistors is (in multiple ways)  representable as a binary tree.  The trees appearing in the axioms of dilatation structures are  different from the ones appearing in the axioms of boolean algebras,  but the question remains: find interesting circuits and their algebra,  but for dilatation structures.  So I have a question to ask you: if you think about dilatation gates as  elementary molecules, what is their chemistry? That is, have you seen  (binary) trees and/or algebraic rules involving such objects in chemistry?  Is maybe process algebra another ingredient to add? For process algebra see   http://www.lfcs.inf.ed.ac.uk/reports/89/ECS-LFCS-89-86/ and the wiki entry    http://en.wikipedia.org/wiki/Process_calculus  I would appreciate any help/idea.

feb 12, 2010:   Otherwise, concerning my last mail, now  I have an answer, namely dilations in  metric spaces are approximate quandle  operations (Reidemeister move III is  true in the limit of the rescaling which  gives the tangent space)! It is somehow natural,  if you think about the Alexander quandle, which  is an “exact” quandle due to the linearity, and  the quandle operation is just an Euclidean dilation.  Sorry that I can’t  explain more precisely in few words,  but this means that there is a whole algebraic avenue  to explore!

jun 10, 2010:       This is just to communicate some ideas about  what means to simulate (computations in) a space,  which I discovered that seems to be related to  some  viewpoints in studies of human vision,  like Koenderink’ “Brain a geometry engine”.

Spiral patterns in the full zipper graph (another post on the Chemical concrete machine)

A step for making something analogous to the Holliday junction, such that it is related to the Chemical concrete machine minimal formalism, is to make a full zipper. Let’s play with it.

I shall use two ingredients, which function only by using the graphic beta move, so I shall NOT use the FAN-IN move.

fullzipper_1

  • zippers, this time written with the conventions of the Chemical concrete machine minimal formalism.

fullzipper_2

If we put them together then we obtain graphs like this: (ignore for the moment the red and green curved  arrows, suppose they are not there)

fullzipper_3

Now, if we want the numbering 1-1′ 2-2′ 3-3′  to make sense, we may add arrows, the green and red ones. But mind you, we could also add graphs with one input and one output instead of each green or red arrow.  As usual, the colours are just a visual help, they mean nothing in the formalism.

Is just a play, but for the moment, since it’s holiday season, I like to think about the green and red arrows (in fact about their replacements by graphs with one input and one output) as being the letters A, C, G, T. Of course, it might mean nothing, let’s see, it’s just a vague hypothesis.

Left for play: draw a Holliday junction.

Ancient Turing machine helps Chemical concrete machine

In this post I want to prove that only with arrow molecules and enzyme moves we can generate all we need for the chemical concrete machine, by using the minimal (?) formalism from  Chemical concrete machine, short list of gates and moves . This is done with the help of ideas from the old post   Ancient Turing machines (I): the three Moirai, which   contains a discussion about generating moves for graphic lambda calculus.

In the post Local FAN-IN eliminates GLOBAL FAN-OUT (II) , at the end, I prove a switch move from CO-COMM and FAN-IN moves. In the next figure, I call this move (which is, recall, a “macro move”, made by a succession of three moves) SWITCH.  In the same figure appears a move CREA’. The name is justified by the resemblance with the CREA move proposed in Ancient Turing machines (I): the three Moirai .

recrea_2

Before giving the proof of CREA’, let me remark that from these macro moves, together with the ones selected in the post  Chemical concrete machine, short list of gates and moves , we can recover all the generating moves of the three Moirai described in the ancient Turing machine post. For example, CREA’ , used for a triple of arrows, gives both the  Clotho’s  CREA  original move and the Atropos  GARB move.

Here is the proof of CREA’:

recrea_1

From a bag of arrows at our discretion, this move gives us fan-out gates and termination gates.  Moreover, it is pleasant to see that, as the SWITCH move is a consequence of CO-COMM and FAN-IN, the CREA’  move is a consequence of CO-ASSOC and FAN-IN.

We need the other three trivalent gates, let’s see how we can obtain them (generate them from arrows, by using moves, recall that moves are enzymes, in the world of the chemical concrete machine).

The fan-in gate is generated like this (we already generated termination gates):

recrea_3

The lambda abstraction and application gates can be generated by using the graphic beta move and a SWITCH move.

recrea_4

Now we have all the gates we need and we can proceed to constructing whatever combinator we want from them, mainly by using SWITCH moves. One elegant way for doing this would be to construct zippers first, by using the graphic beta moves, then construct the S,K,I combinators from zippers, as indicated in  Combinators and zippers.

Probably, the real chemical concrete machine will function with terms (molecules) created by some more natural chemistry tricks, but it is pleasant to see that in principle we can also construct what we need, before passing to the “computation” part, only by using arrows and moves.