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

More details about the Game of Research and Review

What  would you get by combining gamification with visual representations of the peer-review process? A Game of Research and Review.

That’s a follow-up of the post MMORPGames at the knowledge frontier, with more details about how it could work, as a possible solution for making people want by themselves to do the peer-review. (See also the posts Gamifying peer-review?   and We, researchers, just need a medium for social interaction, and some apps .)


I propose another rewarding mechanism than points, a more visual one. First, the articles, according to their keywords, produce a 2D landscape, in principle by the same procedure as this old clickable map of mathematics:

Then, reviewing an article is like claiming property of a piece of land in this world. The value of the claim itself, depends on others opinion about your review.

Instead getting points, you own (shares, say, of) a territory.

Finally, there should be a sort of market for selling-buying property (i.e. shares of some piece of land), which is also automatically mediated by setting a minimal value of a piece of land as function of how connected it is (for example, if you “own” shares over 5 articles, the minimal value of that composite piece of land increases with the number of connections of these articles with other articles you don’t have, or sell). This gives a mechanism of increasing the value of a piece of land simply by adding articles which connects previously unconnected other articles.

The soft needed for this exists, I suppose. Moreover, a visual representation is much more impressive than a number (of points) and it raises more primitive reactions in the users brains.

Teaser: B-type neural networks in graphic lambda calculus (I)

Turing introduced his A-type and B-type neural networks in his 1948 technical report Intelligence Machinery.    Read more about this from Turing’s Neural Networks of 1948, by Jack Copeland and Diane Proudfoot.

This post is the first in a series dedicated to a new project which I intend to launch after the summer break (or earlier, let’s see how much I can hold on). One of the goals of the project is to design, as a proof of principle, neural networks in graphic lambda calculus.

As a teaser, I want to describe how to build B-type neural networks, more precisely how to build a richer version of those.

By a B-type NN I mean a dynamical graph which is made by neurons and connections. Let’s take them one by one.

1. Neurons .  In graphic lambda calculus a neuron is a particular type of graph which has the following form: (in a simpler form neurons appeared from the inception of the graphic lambda calculus)


The body of the neuron is any graph A \in GRAPH with several inputs and one output.

The axon is a tree of \Upsilon gates, but not the original ones, but those from the freedom sector of the graphic lambda calculus. In a moment I shall recall the notations from the freedom sector.

Likewise, the dendrites are “half-arrows” from the same sector. This is needed because the body of the neuron does not have to be in the freedom sector.

2. Notations from the freedom sector. Here they are:


The “yellow” gates from the freedom sector behave exactly like the original ones, but in this sector we can cut and paste at will the wires between these gates, by three graphic beta moves:


HOWEVER, the previous figure does NOT describe a connection. These are for the next time.

Dictionary from emergent algebra to graphic lambda calculus (III)

Continuing from   Dictionary from emergent algebra to graphic lambda calculus (II) , let’s introduce the following macro, which is called “relative \Upsilon gate”:


If this macro looks involved, then we might express it with the help of emergent algebra crossing macros, like this:


Notice that none of these graphs are in the emergent algebra sector, a priori! However, by looking at the graph from the  left, we recognize an old friend: a chora.  See arXiv:1103.6007 section 5, for a definition  of the chora construction, but only in relation with emergent algebra gates. Previously the chora diagram appeared as a convenient notation for the relative dilation gate, but here we see it appearing in a different context. It is already present in relation with lambda calculus in the lambda-scale article arXiv:1205.0139  , section 4.  It will be important later, when I shall give an exposition of the second paragraph after Question 1 from the post Graphic lambda calculus used for quantum programming (Towards qubits III) .

With the help of the relative \Upsilon macro, we can give a new look at the mystery move from the end of dictionary II post. Indeed, look at the following succession of moves:


The use of the mystery move is to transform the relative \Upsilon gate into a usual \Upsilon gate! So, if we accept the mystery move for the emergent algebra sector, then the effect is that the relative \Upsilon gate is in the emergent algebra sector of the graphic lambda calculus and, moreover, it can be transformed into a \Upsilon gate.

With this information let’s go back to the graphs A and C from the dictionary II post.


We know that A \leftrightarrow C in the emergent algebra sector is the right translation of the approximate associativity from emergent algebras (formalism using binary trees, for example). In the last post we arrived at the conclusion that we can prove A \leftrightarrow C by using the mystery move as a legal move in the emergent algebra sector of the graphic lambda calculus (in combination with the other valid moves for this sector, but not using GOBAL FAN-OUT).

Instead of the graph C, we may  introduce the graph C' and compare it with the graph C:


The only difference between C and C' is  given by the appearance of the relative \Upsilon gate, in C', instead of the regular \Upsilon gate in C.


We can prove  that  C' \leftrightarrow A. In particular this proves that C' is in the emergent algebra sector, even if it contains a relative \Upsilon gate. Recall that  if we don’t accept the mystery move in the emergent algebra sector, then it’s not clear if it belongs to that sector.  The proof is not given, but it’s straightforward, using the moves CO-ASSOC, CO-COMM, LOC PRUNING, R2 and ext 2 (therefore without the mystery move).

We can pass from C' to C by using the fact that the mystery move allows to transform a relative \Upsilon gate into a regular one. So this is the way in which enters the mystery move in the equivalence A \leftrightarrow C: through A \leftrightarrow C' , which can be done without the mystery move, and C' \leftrightarrow C by the mystery move, under the form of transforming a relative gate into a regular one.

Is 3D Cube a predecessor of UD?

Pablo Hugo Reda has found this old site dedicated to the 3D Cube Project (that’s an even older link sent by appc23, with more access to info), as well as a discussion on the net which looks strangely alike the actual exchanges around UD.  There are an exe and a database, as well. I reproduce further some parts, taken from the two links provided by Pablo  (only boldfaces by me):

3DCube is as far as I know, a completely different way to store and display complex 3D images. The building atoms of the 3D data structure are lines of pixels, not polygons, bitmaps, or voxels. As explained above, the main objective of the project was to create a system that would allow very complex, elaborate models, with hundreds of structures, which could take up to an entire CD-ROM but require only a small portion of the model to reside in RAM. A large portion of the challenge was coming up with data organization that would allow keeping the model on CD ROM but be capable of displaying the perspective of the entire model instantly at any time. This is possible since the high detail of the model is only needed for elements close to the view point origin. Almost no processing is needed to load the model or its parts from the disk (please notice how quickly the demo initializes). Therefore, the disk activity processing load related to tracking the view point movement is very small – much lower than required for playing a digital video for example.

The algorithm required to display the image at any angle from the view point is quite simple. No floating point calculations, trigonometric functions, or even division instructions are needed, and use of multiplication instructions is very limited. A simple custom hardware utilizing my method could render the image with the same ease as a video card hardware displays the bitmap stored in its video memory. […]

My rendering algorithm is essentially a DSP-type algorithm, working with 64-bit data, which generates the image scan-line by scan-line with operations being mostly adding of 64-bit data. If the 80×86 just had a few more registers, the entire rendering algorithm would use no temporary RAM data (just the CPU registers) and would render the entire image by reading the model and outputting the resulting scan-lines. The biggest current problem in implementing the algorithm now is the necessity to swap the temporary data in and out of the registers to memory.

3D Cube project was originated with the intention of making it a new generation 3D game engine, allowing unprecedented detail and complexity of “virtual worlds” created. After seeing the performance and model sophistication possible with this method, I realized that the possible applications of the method are far beyond just video games. […]

In addition to the above, 3D Cube could allow things like taking pictures of some scene from different directions, building a model out of it. 3D Cube storage method

It’s not a mistake, the text ends like this.

From the discussion, a comment by the 3D Cube creator, S.A. Janczewski:

Well, let us try to clarify the term voxel.
– If a “voxel” can have different color/attribute from each of 6  directions, is it still a voxel?
– If it is not cubical — can have sloped surfaces, is it still a  voxel?
– If the six colors of a “voxel” are not at all stored together as a unit, is it still a voxel?
If the data organization of a 3D engine does not have any kind of  data structure that would store data through clear (x,y,z) – coordinate
granularity, is it still a voxel engine?

If you answer yes to all the above questions than my engine is a voxel engine but so is any polygon-based engine.

I hope that the above will make it clear that the reasons I did not use  the term voxel anywhere were following:
– My method has absolutely nothing in common with commonly known voxel engines or storage techniques
– Since the term voxel is not clearly defined, using it would not  contribute anything(rather than confusion) to the descriptions
– Some “voxel engine” techniques are patented — using the term could result in getting myself (without a reason) accused of “patent infringement.”

Please forgive me if you somehow interpreted my previous message as   criticism of your input. I did however get accused quite a few time of ignorance (not by you) for not using the term voxel in my description  and felt it was appropriate to respond to it.

What do you think?


UPDATE: Is maybe relevant for the discussion to state that the goal is to produce an open source variant of an UD like algorithm. As you can see, supposing of course that 3D Cube was indeed a precursor of UD, the problems are the same, i.e. a probably very good idea, with a lot of potential for cash and also a game changer for an industry. Communicating it means loosing an advantage, but not communicating it leads to disbelief. There is a third way, open source. Right, no direct money from it, but everybody benefits and new possibilities open. So, in case you are working on that, don’t be shy or secretive, that’s not the good idea. Share.

Dictionary from emergent algebra to graphic lambda calculus (II)

This post continues the Dictionary from emergent algebra to graphic lambda calculus (I).     Let us see  if we can prove the approximate associativity property (for the approximate sum) in graphic lambda calculus.  I am going to use the dictionary and see if I can make the translation.

With the dilation structures/tree formalism, the approximate associativity, with it’s proof, is this:


Let’s translate the trees, by using the dictionary.


At first sight, the graphs A and C are clearly in the emergent algebra sector of the graphic lambda calculus. For the graph B, which corresponds to the tree from the middle of the first figure, it’s not clear if it belongs to the same sector.

The next figure shows that it does, because we can pass from A to B by a succession of moves acceptable in the sector.


Problems appear when we try to relate B and C. The reason of these problems, we shall see, is the fact that we renounced at having variables, by employing  the “fan-out” gate \Upsilon. But this gate is a fan-out only in a very weak sense, in fact is more like a co-commutative co-monoid operation.

Let’s see, we prepare B in order to be more alike C.


There is a part of the final graph which is encircled by a green dashed line, pay attention to it.

We prepare now C a bit:


The graph from the right has also an encircled part in green. Look close to this graph, in parallel with the last graph from the preparation of B. We remark that these two graphs are the same outside of the respective encircled regions. If we could transform one encircled region into the other then we would have a proof that B \leftrightarrow C.

In conclusion, the mystery move


would solve the problem of proving the approximate associativity in the emergent algebra sector of the graphic lambda calculus. Remark that if \Upsilon would really be a fan-out gate, i.e. if we could apply to it GLOBAL FAN-OUT moves, then the mystery move would be true.

But I don’t want to use global moves in the emergent algebra sector, because in the tree formalism all moves are local. Moreover, even with global fan-out, in order to be able to apply it, it would be necessary that at the labels “x” and “u” to be grafted graphs which have no connection in common, therefore, strictly speaking, we succeed to prove an approximate associativity weaker than the approximate associativity from emergent algebras/tree formalism.  (The same phenomenon, but for another identity of emergent algebras, is explained in this post.) The reason is in the apparently innocuous but hard to manage fact that we renounce of having variables in graphic lambda calculus.

Next time, about the meaning of the mystery move.