All posts by chorasimilarity

can do anything

Molecular computers

Can you believe that such a complex, intricate sequence of hundreds of chemical reactions is possible, in the right order, in the presence of randomness and without any assistance from a human director? At a molecular level?

Yes, it is possible. Here is why.
What you see in this video is a virtual molecule, which enters in random chemical reactions in a soup of invisible enzymes. All chemical reactions consist in the enzymes interacting with a small number of atoms (color coded in the video), in a random order, and facilitating certain, well chosen reactions.
Everything is purely local, there is nothing else behind the scenes.
And still it works.
This is not real chemistry (but who knows? I believe it is, with the condition to identify real chemical reactions like those virtual ones).
The chemical reactions needed are listed at this page.

If you want to play with this (made-up) chemistry, called “chemlambda”, then go to the github repository

clone it and just type:
and then choose one of the molecules, encoded as .mol files, from the list.
There are a bunch of demos, which show animations for different molecules, made in d3.js, at the link

What is different in this video, which is a screen recording at 4X speed of an animation made with the script, is that it is now possible to see the virtual molecules as made of “atoms” (they may be smaller, well chosen molecules themselves).
This is possible because of a modification of the script called by the sh script, i.e. the awk script check_1_mov2_rand_metabo.awk .
The visualization of the “true” virtual atoms is realized by representing the chemlambda nodes and their ports according to a color scheme which uses the “all_nodes_atom” field of the nodes and ports.

UPDATE: here is d3.js demo page for that.


How to put a Y combinator into a neuron and lock it with a quine

I mentioned before that the Y combinator, seen in chemlambda, is a gun which shoots pair of fanout and application nodes. No more, no less.

The problem is then how to dispense with the Y combinator once we don’t need it any more.

The mentioned solution is to lock it into a quine. Here is how.

First, we put the combinator (in its purest, two nodes form) into a neuron architecture.


What we see: the pale blue dot from the upper right part of the picture is a FROUT (free out) port.

  • NEURON AXON: connected to the free out is a pair of nodes which IS the Y combinator as seen in chemlambda (see this old demo of the reduction of the Y combinator to this pair of nodes, which after starts to shoot; I’ll probably add a page for this reduction at the demos site, this time with the new color convention, and for the chemlambda version with FOE nodes, but the old demo explains sufficiently well the phenomenon) .
  • NEURON SOMA: in this example the soma is made by one green node (is an application A node), but more sophisticated graphs are acceptable, with the condition to be propagators (i.e. to “propagate” through FO or FOE nodes after a sequence of chemlambda moves; one can transform any lambda term expressed in chemlambda into a propagator)
  • NEURON DENDRITES: in this example there are two dendrites, because the soma (A node) has two in ports. The dendrites have FRIN (free in) ports which can be connected to other graphs. In the picture the FRIN nodes are color coded.
  • DENDRITES ENDS: at the end of each dendrite there is a small molecule, well chosen.

With the random reduction algorithm the following happen (see the demo in d3.js)

  • the NEURON AXON grows and becomes a string of copies of the SOMA with the free in ports attached to it (check out that the colours match!) This is the way we use the Y combinator!
  • when the dendrites are consumed, the graph built at the axon detaches from the rest of the neuron
  • there are now two graphs, one is the one built at the axon and the other is the one which still contains the Y combinator gun,
  • the DENDRITES ENDS, together with the SOMA, lock the Y combinator (i.e. the NEURON AXON) into a quine, i.e. they form together a quine
  • the quine is chosen to be one which does not live long (from a probabilistic pov) so it dies after producing some bubbles (i.e, some Arrow elements with the in connected to the out or to other Arrow elements).



Another chemlambda reduction and a weird Google bug


This is the end of the computation of the monus function monus(a,b)=a-b if a>=b, else 0, for a=3 and b=20.

It is the last part of the computation, as recorded at 8X speed from my screen.

If you want to see all of it then go to , clone it and then type: bash and choose monus.mol from the list of mol files.

It is used the deterministic algorithm, this time, which makes all possible moves every time.

What is interesting about this computation is the quantity of trash it produces.

Indeed, I took a lambda term for the monus, applied it to 3 and 20 (in Church encoding), then applied it to successor then applied it to 0.

In the video you see that after the result (the small molecule connected to the blue dot, it i sthe chemlambda version of 0 in the Church encoding), there is still a lot of activity of destroying the rest of the molecule. It looks nice though.

Something strange happened when I tried to publish the video (there are so many strange things related to the dissemination of chemlambda that they become a family joke, some of the readers of this blog are aware of some of those).

After I completed the description I got the warning shown in the following video:  “Brackets aren’t allowed in your description”


For example this previous video has brackets in the description and in the title as well

and all worked well.

Anyway I eliminated the brackets but the warning remained, so eventually I got out from my google account and done something else.

Sometimes later I tried again, experience described in this video (which took a LOT of time to be processed)

At the beginning the fields for title and description were void and no error was announced.

After I filled them happened what you see in the video.

I understand that Google uses a distributed system (which probably needs lots of syncs, because you know, that is how intelligent people design programs today), but:

  • the “brackets are not allowed” is bogus, because a previous video worked perfect with brackets in the description,
  • the “unknown error” means simply that there was some trace left on my computer that there was an imaginary error in the previous try, so instead of checking if there is an error this time, I suppose that the browser was instructed to read from the ton of extremely useful cookies google puts in the user’s place.


The shuffle trick, or how to eliminate commutativity and associativity, for the benefit of better self-multiplication

 On a set with an operation which has a neutral element, there is an algebraic axiom which is equivalent with both associativity and commutativity of the operation. I call it the shuffle (does it have a name?).
It is this one:


(ab)(cd) = (ac)(bd)


so the middle terms b and c switch their position.

Of course, by duality, that means that there is an axiom which is equivalent with both co-associativity and co-commutativity, in an algebra with co-unit.

This is a justification for the existence of TWO fanout nodes in chemlambda, called FO and FOE. The graphical representation of the shuffle, called now the shuffle trick, is simply a combination of two graph rewrites, as shown in the demo on the shuffle trick.
On this blog the shuffle trick is mentioned several times, and the “shuffle move” is proposed as various compositions of moves from graphic lambda calculus.
But the CO-COMM and CO-ASSOC moves from graphic lambda calculus are no longer needed, being replaced by FO-FOE and FI-FOE (aka fan-in) moves. This is good because the graph rewrites which express the associativity and commutativity are too symmetric, they don’t have a natural direction of application, therefore any choice of a preferred direction would be artificial.
The shuffle trick is essential for self-multiplication, where there has to be a way to multiply trees made by FO nodes, in such a way so that the leaves of the copies of the tree are not entangled, see this demo.

What chemlambda can do for you

This post follows after What can I do with chemlambda, which questions to ask about it? and FAQ: chemlambda in real and virtual worlds.

1. Is chemlambda another visualization tool for lambda calculus?

NO. Visualization is an independent part, for the moment I use d3.js. Moreover chemlambda is only tangentially related to lambda calculus.

2. What is new in chemlambda then?

You have an example of a computation model which does not use values, calls, variables, variable passing.

Have you seen any other model with these properties?

3. Why should I be excited about a computation with no values, no evaluations, no calls, etc?

For several reasons:

  • nobody thinks about that (excepting perhaps biology related researchers, who don’t see, by looking through the microscope, the structure loved by CS people)
  • this is a blind spot, an accident of the history, because computers appeared after the telephone, during and after the WW2 when the problem was to encrypt and decrypt a message sent from A to B, and because physically the computers we know how to build are based on electronics
  • think, if you don’t have the problem of how to pass a value, or how to call a function in the internet, then what could be possible which now is not?
  • think about building real or virtual computers which are life like, in the sense that their work is complex to the point of seeming incomprehensible, but their complexity is based on very simple mechanisms, used again and again, without any director to channel them and without any hierarchy to maintain or enforce.

4. So should I pack my bags and look for other research subjects than what is popular now, or maybe should I just ignore chemlambda and go with the business as usual? After all, you know, cloud computing is great. Process calculi, types, all this.

It’s your choice, but now you know that there is something which is closer to real life like computation, which may hold the promise for a free sky, cloudless internet.

5. Suppose I want to play a bit with these ideas, but not to the point of getting out of my comfort zone. Which questions would be interesting to ask?

Right, this is a good strategy. Here are some questions which are related to lambda calculus, say.

  •  there is an algorithm which transforms a (untyped lambda beta calculus) term into a chemlambda molecule, but even if one can prove that beta move translates into the BETA move (like Wadsworth-Lamping) and that eventually the translations of SKI or BCKW combinators reduce in chemlambda like they should, there is the question: how does chemlambda does by local writes the thing which replaces  an evaluation strategy? A study by examples may give interesting insights.
  • how to program with chemlambda? Indeed, it can reproduce some behaviours of untyped lambda beta, but even so it does it in ways which are not like usually expected, as proven by the demos. To take an older example, the Y combinator simplifies to a 2 nodes molecule, story told in this article . The fact is that because one does not have eta (which looks like a global move in chemlambda, i.e. there is no a priory bound on the number of nodes and links to check for application of eta) then there are no functions. It’s a kind of extremal functional programming where there are no functions.
  • (c) what are the right replacements for lists, currying, booleans, which could take advantage from  chemlambda?
  • (d) by a try and explore procedure, which are the less stupid reduction algorithms and in which sense do they work exactly? This has to do with locality, which constrains a lot the design of those algorithms.
  • (e) finally, what can chemlambda do outside the sector of untyped lambda beta, which is only a small part of the possible chemlambda molecules?


The working factorial

Continuing from Experiments with a little lisper tutorial, recall that at that moment I succeeded to compute with chemlambda a relative of the factorial, but not the factorial itself.

Now, I learned how to do it and it works all the time (compared with 20% success last time).

Last time I took a lambda term for the factorial from the lambda calculus tutorial by Mayer Goldberg from the, par. 57, page 14. Then I modified it and got a molecule which computes the factorial in about 20% of the cases. Now, in this working factorial example, I made two supplementary modifications. The first consists in starting from a lambda term which uses the mutiplication in the form L mnf.m(nf) instead of the one used in the tutorial. Secondly, the result of the computation (i.e. the “value” of the factorial) is applied to a SUCC (successor) which is then applied to c0, which result in the generation of the correct result.

Link to the demo with factorial(4)=24.

Here is the video, recorded as seen in safari, with 2X speed (firefox behaves crappy with the d3.js demos I make, have no precise idea why; that is why I recorded my experience with the demo, then re-recorded the video with 2X speed, all this done with QuickTime)

It works very well also with factorial(5)=120, but because the visualization of that computation takes some time (which may challenge people with short attention span), here is a video with the last part of the computation at 8X speed.


What can I do with chemlambda, which questions to ask about it?

[I continue the habit to use sometimes the drafts I write and to extract from them and process a bit those parts which may be of interest to any known or unknown fellow thinker, tinker, hacker.

This is the first part, there will be a second one.]


See also: FAQ: chemlambda in real and virtual worlds


1. Can I play with chemlambda like in the demos?

YES, if you go  at  , then you’ll  find everything needed to play with chemlambda.

What you need:

  • scripts like,  which calls
  • the main program which is check_1_mov2_rand_metabo.awk
  • you need initial molecules, which are  in the files with the extension .mol. Read here about the mol format (1), (2). It’s just a list of nodes and their ports.
  • You shall need also the file firstpart.txt.

Then figure it out:

  • bash asks you to type the name of a mol file, say lalala.mol
  • it produces lalala.html which you can see in the browser, as a d3.js animation.

In the awk script you have at the beginning the variables:  metabo (which decides the color of the new nodes; periodically, with period metabo, the color of the new nodes is turned to #222 or it is left unchanged, in order to help visualize the flow and replenishment of the new nodes in the molecule, i.e. the metabolism of the molecule) and cycount which is the maximum number of steps in the main cycles (if you expect that the computation stops quick, or if on the contrary, you suspect it will never stop, then take cycount=100, if you are sure the computation will stop, but perhaps after more than 100 steps, then take cycount=1000 for example).

The main cycle starts at line 931.

At about the line 900 there is a function nextval()… where there is a piece “return 3000 + (5*step“, now you can modify 3000 to something else to decide the initial time before the animation starts, and 5 to something like 30 or bigger, if you want to look at the result in firefox or if generally the browser has problems with rendering.


For the list of moves and more details see the page of moves. Go down to that page to see a list of articles.


2. Is chemlambda something fixed  or it changes? Can I change it? What can I do if I want to tinker with it, just for fun?

It changes. First there was “graphic lambda calculus”, then there was chemlambda without the FOE node and moves, now after many experiments there is THIS chemlambda.

You can change it any way you want (and be polite to cite my version and to notice me somehow, preferably by posting something in a public place).

If you have real programming skills, not like me (I’m just a mathematician) then you can take the awk script and:

  • transform it into a js script, instead of the actual system
  • make it quicker (presently there is a preset of 5ms which decides the speed of the animation, but this may give problems to many browsers; why? I have no idea, but it may be a trivial or a clever fix to that)
  • add a molecule builder UI
  • make a game out of it
  • make an app
  • make a script which converts lambda terms to chemlambda molecules, according to the algorithm from here.

These are immediately useful things to do. There are others too, see next question.

3. What does the script about chemlambda?

The script implements a model of computation based on chemlambda.

So, chemlambda is a purely local graph rewrite system (it is a list of patterns with up to 4 nodes which are replaced by other patterns, perhaps according to rules which involve a condition which can be verified by checking maybe yet another N (a priori fixed, small) links and nodes).

It does not compute by itself, you have to add an algorithm of reductions, which says how to use the graph rewrites, aka the moves.

In the script is used the following algorithm, called in previous post the “stupid” one, because it is really the most simple: after the mol file is converted into a graph (given as nodes and links arrays), after the head of the html file is written, then the algorithm enters a cycle. The structure of this cycle is the following:

  • look for patterns to change, in the order of the graph rewrites priority.  (What’s this priority? It may happen that there are nodes or links which are part of two distinct, but overlapping patterns for graph rewrites. This results into a conflict: which move to apply? By close examplnation of the moves, there is a order of looking for the moves which eliminates the conflicts if we look first at the move FO-FOE, then at the other DIST moves, then at BETA (i.e. A-L) move and FAN-IN (i.e. FI-FOE), then at the PRUNING moves, and each time we find a pattern we put the respective move in a list of proposed moves and we block the nodes so they are not available for being part of other patterns during the search of patterns )
  • do the proposed moves (in the awk script this means to do the moves in the sense of the graph data variables from the script and in the same time, to write in the html file what you just did, in a format intelligible in d3.js)
  • there may be lots of Arrow nodes which appear, and in order to eliminate as many as possible there is an Arrow cycle (see the moves page) which eliminates all Arrow nodes which can be eliminated by COMB moves. (Same thing apply here, you have to write in the html file what you did with the graph during that internal cycle)

This is the stupid deterministic algorithm.

There is a random variant of it, which is exactly what the awk script does.

Whenever a pattern is identified, there is a coin flipped, and with probability about 50% (see further a small detail) the move goes to the list of proposed moves and the nodes are blocked, or not.

In this way the priority of moves is made much less important.

Small detail: there are two kinds of moves, those who increase the number of nodes (DIST) and the others, who decrease the number of nodes (Arrow not taken into consideration). The small detail is that,  after each step of the cycle, the probabilities of the moves are slightly modified so that if in the cycle there has been more DIST moves than the others then the probability of DIST moves decrease, or else if there has been less DIST moves than the others then the probability of DIST move increases in the next cycle.

Why randomness: is a cheap substitute, in this stupid reduction version, for asynchronous.

4. How can I seriously change the  chemlambda reduction algorithm?

By changing from “stupid” to more interesting, it’s up to you. What about bringing into the game Node.js? Know why? because if you look at a mol file, you notice that if you split the file in ten pieces, then each of them is again a mol file.