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

“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?”