All posts by chorasimilarity

can do anything

Symmetries of conflicts

Can you find hidden symmetries in the conflict diagrams of chemlambda? There are now two pages to play with, if you want to help (and have some fun maybe): [1] and [2].

What’s that? Each rewrite/chemical reaction in the artificial chemistry chemlambda has a pattern which triggers the reaction, and then the pattern is replaced by another one by an invisible “enzyme”. Now, the pattern which triggers the reaction is called LP (left pattern).

[3] is the list of rewrites, to be clear!

In chemlambda all LP consist of a pair of nodes, with some ports connected by an external bond (the internal bonds being those which connect the node with its ports). It happens that there exist two pairs of nodes, say LP1 and LP2, which overlap: they have a node in common.

In such a case it means that there are two possible reaction which may happen, but which one will happen? They can’t both happen at the same time, because the patterns overlap and so the results would be incompatible. That’s a conflict.


In a conflict diagram, as the one which is represented here, you see the nodes of chemlambda which enter in he composition of possible LPs, here you see the FI and L (red, but with different colors and radii of ports) FO and A (green, with different ports etc) and FOE (yellow). For each possible LP (i.e. for each rewrite which is triggered by an LP) there is a bond (thin white line) which connects the relevant ports of the pair of nodes of the LP.

What we get is not a chemlambda molecule, because there may be many bonds which connect a port with others. Here for example you see the FOE port middle_in which is connected with 4 other ports, indeed, this is because we find FOE in all DIST rewrites L-FOE, A-FOE, FO-FOE and in the rewrite FI-FOE.

But such a diagram allows to quickly read the possible conflicts.

Now, to symmetries: the conflict diagram shows the role of the nodes not absolutely, but as they enter in relative configurations. Therefore any symmetry of the nodes, ports and bonds (i.e. of rewrites) tells us something about chemlambda which is not obvious in isolation.

For example, I used the conflicts diagram [2] to group the nodes and bonds in order to show that in a sense the rewrites which involve L (the lambda abstraction) and the FI (the fanin node) are “the same”. THere are hints towards an overall symmetry of ports and rewrites in the diagram.

You can find others, in [2] or [3] which has also the node T (here the color of the node is red) and the PRUNING rewrites added.

For this you can move the nodes and fix their position by click and drag, or release them by double click.

Tell me if something seems weird, hidden there.




Do triangulations of oriented surfaces compute?

In a precise sense, which I shall explain, they do. But the way they do it is hidden behind the fact that the rewrites seem non local.

  1. They compute, because ribbon graphs with colored, trivalent nodes and directed edges do compute, via the encoding of untyped lambda terms into this family of graphs, provided by chemlambda. Indeed, a chemlambda molecule is a ribbon graph with these properties. If you want to encode a lambda term into chemlambda then there is a simple procedure: start from the lambda term on a form which eliminates the need of any alpha conversion. Then build the syntactic tree and replace the nodes by A nodes for application and L nodes for lambda abstraction (don’t forget that L nodes have one in and 2 out ports, differently from the syntactic tree node for lambda abstraction). Then eliminate the variables which are at the leaves by grafting trees of FO (green fanout) nodes from the lambda abstraction node to the places where the variables occur, or by grafting T (terminal) nodes to the lambda node which issues a variable which does not occur later, or simply by just erasing the variable label for those variables which are not issued from an abstraction. That’s it, you get a ribbon graph which is open (it has at least the root half-edge and maybe the half-edges for the variables which don’t come from an abstraction), but then you may add FRIN (free in) and FROUT (free out) nodes and think about them as tadpoles and you get a trivalent ribbon graph. The dual of this graph is (equivalent to) a triangulated, oriented surface, which has faces colored (corresponding to the nodes of the graph), directed edges, such that there are no faces with the 3 edges directed in a cyclic way.
  2. How they compute? Chemlambda uses a set of graph rewrites which has some classic ones, like the Wadsworth-Lamping graphical version of the beta move, but it has two types of fanouts (FO and FOE), one FANIN, and different than usual rules for distributivity. Look at the moves page to see them. All these rewrites are local, in the sense that there is a small number, fixed a priori, which is an upper bound for the number of nodes and edges which enter (in any way) into the graph rewrite (as a condition or as the left pattern, or as the right pattern). The algorithm of application of the rewrites is a very important piece which is needed to make a model of computation. The algorithm is very simple, it can be deterministic or random, and consists, in the deterministic case, into the application of as many rewrites as possible, with a priority for the distributivity moves in case of conflict, and in the random case, it’s just random application of rewrites.

Here is an example, where I play with the reduction of false omega id in chemlambda

  1. Now let’s pass to the duals, the triangulated surfaces. The nodes of the triangulated surface correspond to the faces of the ribbon graph. Or the faces of the ribbon graph are global notions, because they are the orbits of a permutation. After one of the rewrites, the faces (of the ribbon graph) change in a way which has to be non local, because one has to compute again the orbits of the permutation for the new graph, and there is no upper bound on the number of half-edges which have to be visited for doing that.
  2. So triangulated, oriented surfaces do compute, but the rewrites and the algorithm of application are hidden behind this duality. They are non-local for triangulated surfaces, but local for ribbon graphs.
  3. Finally, a word of attention: these surfaces do compute not by being arrows in a category. They don’t compute in this usual, say Turaev kind of way. They compute by (the duals of) the rewrites, there is nothing else than triangulated surfaces, colored by 3 colors (red, green, yellow), there is no decoration which actually does the computation by substitution and evaluation. I don’t know why, but this seems very hard to understand by many. Really, these surfaces compute by rewrites on the triangulations, not by anything else.

ADDED: If you look at the tadpoles as pinches, then make the easy effort to see what  the SKI formalism looks like, you’ll see funny things. The I combinator is the sphere with one pinch (the plane), the K combinator is the sphere with two pinches (cylinder) and the S combinator is the torus with one pinch. But what is SKK=I? What is KAB=A? What you see in the dual (i.e in the triangulation) It depends globally on the whole term, so these reductions do not appear to be the same topological manipulations in different contexts.

Res vs objectus

Objects are evidence. If reality is the territory, then objects are on the map.  Objective reality is to be compared with bureaucracy.
If reality is not objective, then how is it? Real, of course. Evidence is a map  of the real. Passive, done already, laid further in the court, ready to be used in the argumentation.
Who makes the map has the power over reality, in the same way as bureaucrats have the power over the people.
The confusion  between res and objectus has very concrete effects in our society.
We communicate on the net via evidence. The technical solutions are these, issued from historical reasons, like wars and analytic philosophy.
We are discontent about the lack of privacy of evidence.
Objects as evidence of happiness are not the same as happiness. We are discontent because objects are not enough, when we are told that they should be.
In this setting, who controls the map making mechanism, who controls the data processing, has the power.
Ultimate bureaucracy presented as the unique way. As the only real way. A lie.

After the IoT comes Gaia

They say that sneakernet does not scale. If you think about the last product of Amazon, the AWS Import/Export Snowball, this clumsy suitcase contains less than a grain of pollen.

Reason from these arguments:

  • the Internet of Things is an extension of the internet, where lots of objects in the real world will start to talk and to produce heaps of data
  • so there is a need for a sneakernet solution in order to move these data around,  because the data are only passive evidence and they need to be processed,
  • compared though with biology, this quantity of data is tiny
  • and moreover biology does not function via signal transmission, it functions via signal transduction, a form of sneakernet,

you’ll get to the unavoidable conclusion that the IoT is only a small step towards a global network which works with chemical like interactions, transports data (which are active themselves) via signal transduction and it extends the real world biology.

After the IoT comes Gaia. A technological version, to be clear.

Some time in the future, but not yet when we could say that the Gaia extension appeared, there will still be a mixture of old ways IoT and new ways biological like. Maybe there will be updates, say of the informational/immunity  OS, delivered via anycasts issued from  tree like antennas, which produce pollen particle. The “user” (what an ugly reductionistic name) breaths them and the update start to work.

The next scene may be one which describes what happens if somebody find out that some antennas produce faulty grains. Maybe some users have been alerted by their (future versions of) smartwatches that they inhaled a possible terminal vector.

The faulty updates have to be identified, tracked (chemically, in real world) and anihilated.

The users send a notification via the old internet that something is wrong and somewhere, perhaps on the other side of the planet, a mechanical turk identifies the problem, runs some simulations of the real chemistry with his artificial chemistry based system.

His screen may show something like this:


Once a solution is identified, the artificial chemistry solution is sent to a Venter printer close to the location of the faulty antenna and turned real. In a matter of hours the problem is solved, before the affected users metabolisms go crazy.

Local machines

Suppose there is a deep conjecture which haunts the imagination of a part of the mathematical community. By the common work of many, maybe even spread over several centuries and continents, slowly a solution emerges and the conjecture becomes a theorem. Beautiful, or at least horrendously complex theoretical machinery is invented and put to the task. Populations of family members experienced extreme boredom when faced to the answers of the question “what are you thinking about?”. Many others expressed a moderate curiosity in the weird preoccupations of those mathematicians, some, say, obsessed with knots or zippers or other childish activities. Finally, a constructive solution is found. This is very very rare and much sought for, mind you, because once we have a constructive solution then we may run it on a computer. So we do it, perhaps for the immense benefit of the finance industry.

Now here is the weird part. No matter what programming discipline is used, no matter which are programmers preferences and beliefs, the computer which runs the program is a local machine, which functions without any appeal to meaning.

I stop a bit to explain what is a local machine. Things are well known, but maybe is better to have them clear in front of the eyes. Whatever happens in a computer, it is only physically local modifications of it’s state. If we look at the Turing machine (I’ll not argue about the fact that computers are not exactly TMs, let’s take this as a simplification which does not affect the main point), then we can describe it as well as a stateless Turing machine, simply by putting the states of the machine on the tape, and reformulating the behaviour of the machine as a family of rewrite rules on local portions of the tape. It is fully possible, well known, and it has the advantage to work even if we don’t add one or many moving heads into the story, or indirection, or other ingredient than the one that these rewrites are done randomly. Believe it or not (if not then read

Turing machines, chemlambda style

for an example) but that is a computer, indifferently of what technological complexities are involved into really making one.


(this is an animation showing a harmonious interaction between a chemical molecule derived from a lambda term, in the upper side of the image, and a Turing machine whose tape is visible in the lower side of the image)

Let’s get back to the algorithmic form of the solution of the mathematical problem. On the theoretical side there are lots of high meanings and they were discovered by a vast social collaboration.

But the algorithm run by the computer, in the concrete form it is run, edits out any such meaning. It is a well prepared initial tape (say “intelligently designed”, hope you have taken your daily dose of humour), which is then stupidly, randomly, locally rewritten until there’s no more reaction possible. Gives the answer.

If it is possible to advance a bit, even with this severe constraint to ignore global semantics, then maybe we find really new stuff, which is not visible under all these decorations called “intelligent”, or high level.


Life at molecular scale

Recently there are more and more amazing results in techniques allowing the visualization of life at molecular scale. Instead of the old story about soups of species of molecules, now we can see individual molecules in living cells [1], or that the coiled DNA has a complex chemical configuration, or that axons and dendrites interact in a far more complex way than imagined before. Life is based on a complex tangle of evolving individuals, from the molecular scale onwards.

To me, this gives hope that at some point chemists will start to  consider seriously the possibility to build such structures, such molecular computers [4] from first principles.

The image is a screencast of a chemlambda computation, done with quiner mist.


[1] Li et. al., “Extended Resolution Structured Illumination Imaging of Endocytic and Cytoskeletal Dynamics,” Science.

[2] Structural diversity of supercoiled DNA, Nature Communications 6,Article number:8440doi:10.1038/ncomms9440,

[3] Saturated Reconstruction of a Volume of Neocortex, Cell, Volume 162, Issue 3, p648–661, 30 July 2015
and video:

[4] Molecular computers