Can graphic lambda calculus be implemented in some form of DNA computing?

I have this question, please spread it if you are not directly interested. Thank you for giving me any informed input (like, for example, “there is this group doing functional programming with DNA”, but  not like “google for DNA community”, because I already did such obvious things).
It just occurred to me that the moves of the graphic calculus introduced in Graphic lambda calculus, to appear in Complex Systems,  which contains a part which is equivalent with untyped lambda calculus, can be seen as chemical reactions between 4 or 5 molecules (and maybe some catalysts).

This graphic calculus works with trivalent graphs, which are assemblies of trivalent gates (thus molecules). Moves, like the main move, graphic beta move,  which is the correspondent of beta reduction in lambda calculus, are local modifications of such graphs, and these moves look like chemical reactions. As concerns lambda calculus terms, they appear as certain graphs. The calculus is purely functional, everything is a graph or a move between graphs, and there are no variable names.

Question: can this be used by  DNA computing, or other type of molecular computing, seen that graphic lambda calculus is naturally fit for this?

(Because it does not care or need any language-like conventions, like words or 1-dimensional manipulations of strings.)

See also, for more details, the tutorial.


UPDATE: Mike Stay points to the article “G. Berry and G. Boudol. The chemical abstract machine. Theoretical Computer Science, 96(1):217–248, 1992”, thank you! I’ll come back to this in a future post.

UPDATE 2:  R.J. Lipton worked on DNA computing. Having moreover a blog post called “It Takes Guts To Do Research” (very interesting, it’s about Oppenheimer and contains  post factum judgements concerning missed opportunities to recognize great discoveries in the physics of his time),  I took the chance to ask about this.  The comment is awaiting moderation since 28 June, appeared July 1st,  so I am posting it here.

“Actually, I do have a question which is maybe natural to ask here. From what I know, visual, diagrammatic representations of lambda calculus are used mostly for fun or for teaching purposes. Trying to understand some geometric phenomena, I constructed such a visual representation, called graphic lambda calculus, which is a formalism working with trivalent locally planar graphs (think about lambda calculus terms) and moves between those (like beta reduction), which are local. Moreover, the formalism has no variables names. Or, it recently occurred to me that the moves look very much alike simple chemical reactions (maybe some catalysts excepted), involving some unknown molecules (the trivalent nodes, or gates, forming the graphs). Looking a bit in the direction of DNA computing, I have not been able to locate any work trying to implement anything like reduction of lambda terms into a chemical computation. This might be due to my ignorance, but I think the question of doing lambda calculus with molecules could be interesting, seen that a graphical formalism for lambda calculus which is free from any 1D constraint (like using words and manipulation of 1D strings), without variable names, might be more fit for such a task than the standard one. What do you think about this?”


4 thoughts on “Can graphic lambda calculus be implemented in some form of DNA computing?”

  1. Just by way of remote associations, there is the theme of “Chemico-Algebraic Theory” that goes back to Sylvester, Clifford, Kempe, and Peirce. The Peirce variations led to his work on logical graphs, developed to the greatest extent in his system of Existential Graphs, which enjoy several lines of active development today.

    At another level, the zipping and unzipping of DNA molecules and the like has always seemed to me especially suited to carrying out unification-type processes.

      1. The judgment of history (so far) on the chemico-algebraic theory of invariants is that it was something of a dead end, but I don’t know if anyone has looked into the macro-molecular angle on that.

        The best introduction to Peirce’s logical graphs would be Don D. Roberts (1973), The Existential Graphs of Charles S. Peirce, but there is a lot on line that any search on relevant keywords would turn up. J.J. Zeman has a lot of stuff online. John Sowa’s Conceptual Graphs also spin off from Peirce’s graphs. My work using cactus graphs arose from focusing on the propositional calculus level of Peirce’s graphical syntax and trying to make it more efficient and more “reflective”.

        There is a good list of references here.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s