Category Archives: distributed GLC

Busy beaver’s random church

The demo linked here would surely look impossible.

One computer, WHILE IT WORKS, is multiplied into 3 computers which  continue to work, each of them. This feat is done without any higher control and there are never conflicts which appear. All computers work asynchronously (mimicked here by randomness). Moreover, eventually they arrive to read and write on the same tape.

There are no calls, nothing you have seen before.Everything is local, no matter how you slice it into separated parts.



As a handful of slime mold. That’s how smart is the whole net.

I record here, to be sure that it’s read, a message of explanations I wrote today.

Before that, or after that you may want to go check the new chemlambda demos, or to look at the older ones down the page, in case you have not noticed them. There are also additions in the moves page. Most related to this post is the vision page.

“First, I have lots of examples which are hand drawn. Some of them appeared from theoretical reasons, but the bad thing used to be that it was too complex to follow (or to be sure of that) on paper what’s happening. From the moment I started to use the mol files notation (aka g-patterns) it has been like I suddenly became able to follow in much more depth. For example that’s how I saw the “walker”, “ouroboros” and finally the first quine by reducing the graph associated to the predecessor (as written in lambda calculus). Finally, I am able now to see what happens dynamically.
However, all these examples are far from where I would like to be now, they correspond to only the introduction into the matter. But with every “technical” improvement there are new things which appear. For example, I was able to write a program which generates, one by one, each of about 1000 initial graphs made by 2 nodes and follow their reduction behaviour for a while, then study the interesting exemplars. That is how I found all kind of strange guys, like left or write propagators, switchers, back propagators, all kind of periodic (with period > 1) graphs.
So I use mainly as input mol files of graphs which I draw by hand or which I identify in bigger mol files as interesting. This is a limitation.
Another input would be a program which turns a lambda term into a mol file. The algorithm is here.
Open problem: pick a simplified programming language based on lambda calculus and then write a “compiler”, better said a parser, which turns it into a mol file. Then run the reduction with the favourite algorithm, for the moment the “stupid” determinist and the “stupid” random ones.
While this seems feasible, this is a hard project for my programming capabilities (I’d say more because of my bad character, if I don’t succeed fast then I procrastinate in that direction).
It is tricky to see how a program written in that hypothetical simple language reduces as a graph, for two reasons:
  1. it has to be pure lambda beta, but not eta (so the functions are not behaving properly, because of the lack of eta)
  2. the reductions in chemlambda do not parallel any reduction strategy I know about for lambda calculus.
The (2) makes things interesting to explore as a side project, let me explain. So there is an algorithm for turning a lambda term into a mol file. But from that part, the reductions of the graph represented by the mol file give other graphs which typically do not correspond to lambda terms. However, magically, if the initial lambda term can be reduced to a lambda term where no further reductions are possible, then the final  graph from the chemlambda reduction does correspond to that term. (I don’t have a proof for that, because even if I can prove that if restricted to lambda terms written onlly as combinators, chemlambda can parallel the beta reduction, the reduction of the basis combinators and is able to fan-out a term, it does not mean that what I wrote previously is true for any term, exactly because of the fact that during chemlambda reductions one gets out from the real of lambda terms.)
In other cases, like for the Y combinator, there is a different phenomenon happening. Recall that in chemlambda there is no variable or term which is transmitted from here to there, there is nothing corresponding to evaluation properly. In the frame of chemlambda the behaviour of the Y combinator is crystal clear though. The graph obtained from Y as lambda term, connected to an A node (application node) starts to reduce even if there is nothing else connected to the other leg of the A node. This graph reduces in chemlambda to just a pair of nodes, A and FO, which then start to shoot pairs of nodes A and FOE (there are two fanout nodes, FO and FOE). The Y is just a gun.
Then, if something else is connected to the other leg of the application node I mentioned, the following phenomenon happens. The other graph starts to self-multiply (due to the FOE node of the pair shot by Y) and, simultaneously, the part of it which is self-multiplied already starts to enter in reaction with the application node A of the pair.
This makes the use of Y spectacular but also problematic, due to too much exuberance of it. That is why, for example, even if the lambda term for the Ackermann function reduces correctly in chemlambda, (or see this 90 min film) I have not yet found a lambda term for the factorial which does the same (because the behaviour of Y has to be tamed, it produces too many opportunities to self-multiply and it does not stop, albeit there are solutions for that, by using quines).
So it is not straightforward that mol files obtained from lambda terms reduce as expected, because of the mystery of the reduction strategy, because of the fact that intermediary steps go outside lambda calculus, and because the graphs which correspond to terms which are simply trashed in lambda calculus continue to reduce in chemlambda.
On the other side, one can always modify the mol file or pre-reduce it and use it as such, or even change the strategy of the algorithm represented by the lambda term. For example, recall that because of lack of eta, the strategy based on defining functions and then calling them, or in general, just currying stuff (for any other reasons than for future easy self-multiplication) is a limitation (of lambda calculus).
These lambda terms are written by smart humans who stream everything according to the principle to turn everything into a function, then use the function when needed. By looking at what happens in chemlambda (and presumably in a processor), most of this functional book-keeping is beautiful for the programmer, but a a limitation from the point of view of the possible alternative graphs which do the same as the functionally designed one, but easier.
This is of course connected to chemistry. We may stare to biochemical reactions, well known in detail, without being able to make sense of them because things do happen by shortcuts discovered by evolution.
Finally, the main advantage of a mol file is that any collection of lines from the mol file is also a mol file. The free edges (those which are capped by the script with FRIN (i.e. free in) and FROUT (i.e. free out) nodes) are free as a property of the mol file where they reside, so if you split a mol file into several pieces and send them to several users then they are still able to communicate by knowing that this FRIN of user A is connected (by a channel? by an ID?) to that FROUT of user B. But this is for a future step which would take things closer to real distributed computing.
And to really close it, if we would put on every computer linked to internet a molecule then the whole net would be as complex (counting the number of molecules) as a mouse. But that’s not fair, because the net is not as structured as a mouse. Say as a handful of slime mold. That’s how smart is the whole net. Now, if we could make it smarter than that, by something like a very small API and a mol file as big as a cookie… “

You can build pretty much anything with that

Progressing,  enjoy that,  details in few days.

UPDATE: and a nice video about the Omega combinator.



… and there is more.

I took two different reduction strategies for the same artificial chemistry (#chemlambda) and looked what they give in two cases:
– the Ackermann function
– the self-multiplication and reduction of (the ensuing two copies of) the Omega combinator.
The visualization is done in d3.js.
The first reduction strategy  is the one which I used previously in several demonstrations, the one which I call “stupid” also because is the simplest one can imagine.
The second reduction strategy is a random variant of the stupid one, namely a coin is flipped for each edge of the graph, before any consideration of performing a graph rewrite there.
The results can be seen in the following pages:
– Ackermann classic
-Ackermann random
-Omega classic
-Omega random
I’ve always told that one can take any reduction strategy with chemlambda and that all are interesting.




How to simulate an enzyme with a quine in chemlambda (II)

Continues from part (I).

How to simulate a move with a quine. Let’s think.

The starting point is a mol file which describes the graph. Then there is a program which does the reductions. We should see the program (or the specific part of it which does a move) as the enzyme of that move. OK, but a program is something and a mol file is a different thing.

Recall though that chemlambda is Turing universal. That means in particular that for any particular mol file A.mol and any particular program P which reduces mol files there is a chemlambda molecule and a reduction algorithm which simulate how the program reduces the mol file. Kind of a bootstrapping, right?

Yes, but let’s say it again: given A.mol and P there exist B.mol such that P reduces B.mol simulates the computation (P reduces A.mol).

In particular there is a part E.mol of the B.mol file (or more abstractly a subgraph of the molecule B) whose reductions in the “context” B simulate the part of the program P acting on A and doing a reduction.

That part is actually a molecule, just as A, which can be thought as being the enzyme of the move (which is implemented in P).

Then, instead of making a (theoretically possible) algorithm which generates from A.mol and P the file B.mol, etc, instead of that we may do something simpler.

We would like to use a quine as E.mol.

That is because it respects the chemical analogy in the sense that the reduction of E.mol preserves the number of nodes (atoms).

For this we look again at what is a move, and also at what new primitive we need in order to make all this to function.

A move is described by a pair of patterns (i.e. molecules), called LEFT and RIGHT pattern, with the property that there is a pairing between the free ports of the LEFT pattern and the RIGHT pattern.

The move then is implemented by an algorithm which:

  • does a pattern matching for the LEFT pattern
  • then replaces the LEFT pattern by the RIGHT pattern.

(I should add that not any instance of the LEFT pattern in A.mol is replaced by a RIGHT pattern, because there may be conflicts created by the fact that a node of A.mol appears in two different LEFT patterns, so there is a need for a criterion which decides which move to do. I neglect this, you’ll see later why, but roughly I concentrate on the move, because the criterion (or priority choice) is a different problem.)

Aha! We need the possibility to make pairings of edges, or even better (seen the mol format) we need a way to make pairings of ports.

I shall use the notation a:b for such a pairing. Notice that:

  • we see such pairings when we say that x is of type a, i.e x:a (recall that one can see types as pairings between edges of molecules and edges of other molecules which represent types from the Calculus of Constructions)
  • the pairing a:A saying that the edge a belongs to the actor A is a pairing (induces a pairing)  between the edges of a molecule and the edges of an actor diagram in distrubted GLC
  • the pairing a:b, where a is an edge of a molecule and x is an edge of another molecule which represents an emergent algebra term (see the thread on projective conical spaces) says that edge “a” is in place “b”
  • the pairing a:b can be the consequence of a copmmunication; non-exclusively one may think of a:b as a consequence of c?(b) | c!(a)
  • in conclusion moves are particular pairings coupled with an algorithm for associating a LEFT pattern to a RIGHT pattern, pretty much as typing is a pairing with another algorithm, or places (i.e. emergent algebras and their reductions) is of the same kind; the algorithm which does the pairing is a matter of communication procedure and it can be implemented by process calculi, actor models or whatever you like best.

So, let’s pick a small quineas E.mol, like a 9- or 10-quine which has the property that it has one LEFT pattern for (say) beta move and let’s do the following:

  • pair a LEFT pattern from A.mol with the same (pattern matching) from E.mol
  • reduce E.mol  (bootstrapping) and get E’.mol which is identical to E.mol up to renaming some of the port (i.e.edge) names
  • update the pairing (which is akin of the intention of  replacement of  LEFT pattern by RIGHT pattern)
  • let the program in charge of A.mol to rewire (apply the update)

It’s perhaps a too short explanation, will come with details from A to Z next year.

Wish you the best for 2015!


A year review at chorasimilarity, second half

In parallel with the stuff about chemlambda, described in the first half, there was something else happening. I prepared some noted for a talk at the 4th Offtopicarium, in the form of a post here:

Notes for the “Internet of things not internet of objects”

The starting point is that what almost everybody describes as the Internet of Things is actually an Internet of Objects. We don’t want an Internet of Objects, because that would be only the usual accumulation of gadgetry and fads, i.e. only a very limited and uninspired construction. It is as imaginative as a big budget movie or as tasty as a fastfood menu.

Because reality is not objective. Reality is made of things, i, e. discussions between us humans about everything. When a certain agreement (or boredom, or faith, etc) is attained in the discussion, the said thing dies and dries into an object.

Discussions between humans thrive when individualities are respected and where there is a place which allows free mixing of ideas. A space. A theater.

Not the theater-in-a-box of perception, where the space is a scene, the dual of the homunculus, the king of fallacies. Because a scene is not a thing, but an object. On the scene the discussion is replaced by an ideology (see this or, from the scenographer point of view this).

Instead, a Greek theater under the sun could be a good starting point. As a machine which implements a theatrical distributed computing.

In order to do so, a necessary step is to separate computation from meaning. That would be only a small step forward after the separation of form from content principle. That’s a very short post, I reproduce most of it here:

One of the principles which make the net possible, as stated by Tim Berners-Lee,

separation of form from content: The principle that one should represent separately the essence of a document and the style with which it is presented.

Applied to decentralized computing, this means no semantics.

[One more confirmation of my impression that logic is something from the 21st century disguised in 19th century clothes.]

At this point the thread described here meets the one from the first half review: one of the discoveries of chemlambda, seen as artificial chemistry, is that it is possible to make this separation.


I stop here with the second half, there will be surely more halves to come 🙂


Question about public key cryptography with chemlambda

In this post Alice and Bob will communicate through #chemlambda computations.

Alice and Bob have each a mol file: Alice has A.mol and Bob has B.mol.

Step 1.  Alice partitions her file into A1.mol and A2.mol. She keeps A1.mol secret. The partition of the A.mol into two files creates some new free ports in A1.mol and A2.mol. Indeed, recall that free port variables are those which appear only once in the mol file. Thus every port variable which appears twice in A.mol, but only once in A1.mol and once in A2.mol, is not free in A.mol, but is free in both A1.mol and A2.mol. Every such variable corresponds to an edge which goes between a node from A1.mol and a node from A2.mol.

Let’s call these port variables “inner” port variables.



Alice renames all (or some of) the port variables from A2.mol and keeps the correspondence between the new names and the old names of the inner port variables.

Then she reduces only the A2.mol and she publishes it.


The published file, A2_red.mol is a mol file. Alice publishes also the partition of free port variables into inner and outer public free ports.

Important remark.  I see the reduction of the  A2.mol  to the reduced A2_red.mol as an encryption of A2mol. This is not a very accurate point of view, but the idea is that the reduction can be seen as a one way function which is easy to compute, but with an inverse which is hard to compute. More accurately,  chemlambda is universal, therefore the reduction of A2.mol may correspond to any computation. The file  i.e. A2_red.mol represents the result of the computation and A2.mol represents the program which has as result A2_red.mol.

Step 2. Bob takes the file A2_red.mol (which is public) and adds it to his own file B.mol. The file B.mol is secret. He connects the outer free ports of the file A2_red.mol to the free ports of the file B.mol, in a way which he keeps secret.


Then Bob reduces this mol file and obtains a file (A2_red-B)_red.mol. He sends this file to Alice.

Step 3. Alice uses her secret correspondence between public and private inner free ports variables to connect her A1.mol with the mol file received from Bob.

She reduces this file.



What happened?

Let’s look at the whole picture at once.


We have a mol file which is partitioned into three parts A1, A2 and B. Then it is reduced in the following way.

1. First the A1 and B parts of the file are frozen and only the A2 is reduced.

2. Then the wave of reductions spread and now only A1 is frozen and reductions are allowed everywhere else.

3. Finally A1 is unfrozen and the reductions continue in the whole file.

This is what Alice gets after the step 3.


Question: what can Alice learn about B.mol by looking at the result?


 UPDATE:   I started thinking about that since the summer 2014, when Louis Kauffman described a  Rope Ceremony in his visual style, using his characters Cookie and Parabel:


Trying to understand what’s going on, I made [my first] video. Here is it: