Lambda calculus inspires experiments with chemlambda

In the now deleted chemlambda collection I told several stories about how lambda calculus can bring inspiration for experiments with chemlambda. I select for this post a sequence of such experiments. For previous related posts here see this tag and this post.

Let’s go directly to the visuals.

Already in chemlambda v1 I remarked the interesting behaviour of the graph (or molecule) which is obtained from the lambda term of the predecessor applied to a Church number.  With the deterministic greedy algorithm of reductions, after the first stages of reduction there is a repeating pattern of  reduction, (almost) up to the end. The predecessor applied to the Church number molecule looks almost like a closed loop made of pairs A-FO (because that’s how a Church number appears in chemlambda), except a small region which contains the graph of the predecessor, or what it becomes after few rewrites.

In chemlambda v2 we have two kinds of fanouts: FO and FOE.  The end result of the reduction of the same molecule, under the same algorithm, is different: where in chemlambda v1 we had FO nodes (at the end of the reduction), now we have FOE nodes. Other wise there’s the same phenomenon.

Here is it, with black and white visuals


Made by recording of this live (js) demo.

1. What happens if we start not from the initial graph, but from the graph after a short number of rewrites? We have just to cut the “out” root of the initial graph, and some nodes from it’s neighbourhood and glue back, so that we obtain a repeating pattern walking on a circular train track.

Here is it, this time with the random reduction algorithm:


I previously called this graph an “ouroboros”. Or a walker.

2. That is interesting, it looks like a creature (can keep it’s “presence”) which walks in a single direction in a 1-dimensional world.  What could be the mechanism?

Penrose comes to mind, so in the next animation I also use a short demonstration from a movie by Penrose.



3. Let’s go back to the lambda calculus side and recall that the algorithm for the translation of a lambda term to a chemlambda molecule is the same as the one from GLC, i.e the one from Section 3 here. There is a freedom in this algorithm, namely that trees of FO nodes can be rewired as we wish. From one side this is normal for GLC and chemlambda v1,  which have the CO-COMM and CO-ASSOC rewrites


In chemlambda v2 we don’t have these rewrites at all, which means that in principle two diferent molecules,  obtained from the same lambda term, which differ only by the rewiring of the FO nodes may reduce differently.

In our case it would be interesting to see if the same is true for the FOE nodes as well. For example, remark that the closed loop, excepting the walker, is made by a tree of FOE nodes, a very simple one. What happens if we perturb this tree, say by permuting some of the leaves of the tree, i.e. by rewiring the connections between FOE and A nodes.


The “creature” survives and now it walks in a world which is no longer 1 dimensional.

Let’s play more: two permutations, this time let’s not glue the ends of the loop:


It looks like a signal transduction from the first glob to the second. Can we make it more visible, say by making invisible the old nodes and visible the new ones? Also let’s fade the links by making them very large and almost transparent.


Signal transduction! (recall that we don’t have a proof that indeed two molecules from the same lambda term, but with rewired FO trees reduce to the same molecule, actually this is false! and true only for a class of lambda terms. The math of this is both fascinating and somehow useless, unless we either use chemlambda in practice or we build chemlambda-like molecular computers.)

4.  Another way to rewire the tree of FOE nodes is to transform it into another tree with the same leaves.



5. Wait, if we understand how exactly this works, then we realize that we don’t really need this topology, it should also work for topologies like generalized Petersen graphs, for example for a dodecahedron.



This is a walker creature which walks in a dodecaheral “world”.

6. Can the creature eat? If we put something on it’s track, see if it eats it and if it modifies the track, while keeping it’s shape.


So the creature seems to have a metabolism.

We can use this for remodeling the world of the creature. Look what happens after many passes of the creature:



7. What if we combine the “worlds” of two creatures, identical otherwise. Will they survive the encounter, will they interact or will they pass one through the other like solitons?



Well, they survive. Why?

8. What happens if we shorten the track of the walker, as much as possible? We obtain a graph wit the following property: after one (or a finite give number of) step of the greedy deterministic algorithm we obtain an isomorphic graph. A quine! chemlambda quine.

At first, it looks that we obtained a 28 nodes quine. After some analysis we see that we can reduce this quine to a 20 nodes quine. A 20-quine.

Here is the first observation of the 20-quine under the random algorithm


According to this train of thoughts, a chemlambda quine is a graph which has a periodic evolution under the greedy deterministic algorithm, with the list of priority of rewrites set to DIST rewrites (which add nodes)  with greater priority than beta and FI-FOE rewrites (which subtract ndoes), and which does not have termination nodes (because it leads to some trivial quines).

These quines are interesting under the random reduction algorithm, which transform them into mortal living creatures with a metabolism.


So this is an example of how lambda calculus can inspire chemlambda experiments, as well as interesting mathematical questions.

Google translate helps the scholarly poor

Do you know what “scholarly poor” means? I saw this formulation some time ago and it made me ask: am I scholarly poor?

You find this expression in the writings of those who praise Gold Open Access, or in the articles which try to understand the Sci-Hub phenomenon.

Recall that Gold OA means practically that authors pay to publish from funds they receive for research. It’s all in the language: Green OA is not for publication, no sir! Green OA is for archiving. Gold OA is for publication and it may incur costs, you see, which may be covered by the authors. (The readers can no longer be forced to pay, so who’s left?) And the authors pay, not from their pockets, because they are not crazy rich to create and moreover to pay thousands of $ to publish their article. They pay from the funds they receive for reseach, because their bosses, the academic managers, ask them to. These academic managers just love the publishers, be them the traditional ones or this new modern Gold OA blend. They don’t like the Green OA, there’s no money involved, pooh! no value.

Sci-Hub made available practically any scientific article, therefore there is no longer any difference between an article published gratis, but behind a paywall, and an article published for 2000$ and free to read. Both are as easily accessible. IANAL but this is the reality of the world we are living in.

This reality upsets the Gold OA proponents, so they use this expression “scholarly poor” to denote those scholars which don’t have institutional access to the paywalled articles. Because Gold OA proponents love academic managers who are not poor, they ignore the reality that the researchers, in poor or rich (crazy?) academic institutions, all of them would rather read either from Green OA (like arXiv) or from Sci-Hub or from their colleagues who put online their work.

In itself, to name a researcher “scholarly poor” is distasteful.

But Google comes to the rescue! When I first saw this expression I was curious how it translates to French, for example, another language I understand.



Thank you Google Translate! And HAHA. And so poetical!

I checked again, today, when I decided to write this post. I recorded myself using the translate:



Yes, OK, a bit more bland, less poetical, but more  comical for the public at large.

So right, though!





A project in chemical computing and Lafont universality

The post Universality of interaction combinators and chemical reactions ends with the idea that Lafont universality notion, for interaction systems, may be the right one for chemical computing.

These days are strange, every one comes with some call from one of my old projects. (About new ones soon, I have so many things.) Today is even more special because there were two such calls.One of them was from what I wrote in A project in chemical computing page from april 2015. It ends with:

    If you examine what happens in this chemical computation, then you realise that it is in fact a means towards self-building of chemical or geometrical structure at the molecular level. The chemlambda computations are not done by numbers, or bits, but by structure processing. Or this structure processing is the real goal!
     Universal structure processing!

There is even this video about an Ackermann function molecular computer I forgot about.

The idea is that the creation of a real molecule to compute Ackermann(2,2) would be the coolest thing ever made in chemical computing. If that is possible then as possible as well would be an Ackermann goo made from Ackermann(4,4):


In Graphic lambda calculus and chemlambda (III) I comment again on Lafont:

    • Lafont universality property of interaction combinators means, in this pseudo-chemical sense, that

the equivalent molecular computer based on interaction combinators reactions (though not the translations) works

    for implementing a big enough class of reactions which are Turing universal in particular (Lafont  shows concretely that he can implement Turing machines).


In the series about Lafont interaction combinators and chemlambda (1) (2) (3), as well as in the paper version of the article Molecular computers, an effort is made to reconnect chemlambda research with much older work by Lafont. [UPDATE: I retrieved this, I forgot about it, it’s mostly chemlambda v1  to chemlambda v2, see also this post ]

The numberphile microbe and the busy beaver

This is another weirdly named, but contentful post after this one, During an attempt to launch myself into video explanations, I made a post on the numberphile microbe.

The numberphile microbe is the chemlambda version of a multiplication of two Church numbers, in this case 5X5=25. I called the creature evolving in the video a “numberphile microbe” because it really consumes copies of the number 5, metabolizes them and produces eventually 25. In a very careful way, though, which inspired me the following description (but you have to see the video from that post):

“The numberphile microbe loves Church numbers. His strategy is this: never one without the other. When he finds one Church number he looks around for the second one. Then he chains the first to the second and only after that he starts to slowly munch the head of the first. Meanwhile the second Church number watches the hapless first Church number entering, atom by atom, in the numberphile mouth.

Only the last Church number survives, in the form of the numberphile’s tail.”

The  mol file used is times_only.mol.  Yes, allright, is the mol version of the AST of a lambda term.

You can see the numberphile also in this animation, together with a busy beaver Turing machine (the chemlambda version explained here):



In the first half of the animation you see the “numberphile” at the left and the busy beaver as a reddish loop at the right.

What happens is that the lambda term like 5X5 reduces to 25 while in the same time the busy beaver machine works too. In the same time, the Church number 25 in the making already makes the small loop to replicate and to grow bigger and bigger, eventually 25 times bigger.

So that explains the title.

The mol file used is times_only_bb.mol. Open it and see how is it different than the first.

You can see a simulation (js) of Church number applied to a busy beaver here.

And the most important is: during the making of this short movie, no human director was present to stage the act.

Plato, Orwell, Stalin & her exploratory cries

If you google

Plato Orwell Stalin “her exploratory cries”

this uniquely identifies an article I wrote back in in 2010, the year when I discovered  that I have to go in a new direction (for me).

[UPDATE: no longer true, Google  adapted  and now it points  to a number of my pages where there is none of the words searched…]

There are  two different ideas in that article:

  • the hypothesis that (Nature/ brains) use the same mechanism for (building/understanding) space. In today words: space (is/can be understood as)  a semantic (i.e. a decoration by local rules ) of a graph rewrite automaton. Nature runs the automaton probably by sampling from hamiltonian evolution (which does not compute) perturbed by dissipation (and the computer is in the information of the gap from hamiltonian evolution). Brains and more basically living cells run by chemistry, a toy model of the computation model is chemlambda. Those mechanisms are the same, the computer is in the information gap.
  • the second idea is that as concerns brains, biological vision definitely is the creation of a geometry engine, as Koenderink write, but more specifically because  there should be some universal form of  computation which comes from the (formalization of) exploration of space via multiple drafts or maps. There’s where emergent algebras come into play, but this part is not yet completely clear,  because until now I am not sure in all details that I succeded to prove that emergent algebras are universal, either in sense of Turing or Lafont.

That and the collapsing of the wave function is an orwellian theory and the minimal action principle is stalinesque, if we apply to physics the classification of Dennett  of theories of biological vision.

Somewhere in the text you’ll find as well “her exploratory cries”. And a mutant army of bats 🙂

Blockchain categoricitis 2, or life as an investor and a category theory fan

… or the unreasonable effectiveness of category theory in blockchain investments.

A year ago I wrote the post Blockchain categoricitis and now I see my prediction happening.

Categoricitis is the name of a disease which infects the predisposed fans of category theory, those which are not armed with powerfull mathematical antibodies. Show them some diagrams from the height of your academic tower, tell them you have answers for real problems and they will believe.

Case in point: RChain. See Boom, bust and blockchain: RChain Cooperative’s cryptocurrency dreams dissolve into controversy.

Yes, just another cryptocurrency story… Wait a moment, this one is different, because it is backed by strong mathematical authority! You’ll practically see all the actors from the GeekWire story mentioned in the posts linked further.


Guestpost at John Baez blog: RChain (archived)

“Programmers, venture capitalists, blockchain enthusiasts, experts in software, finance, and mathematics: myriad perspectives from around the globe came to join in the dawn of a new internet. Let’s just say, it’s a lot to take in. This project is the real deal – the idea is revolutionary […]”

RChain is light years ahead of the industry. Why? It is upholding the principle of correct by construction with the depth and rigor of mathematics.”


Another one, in the same place: Pyrofex (archived). This is not a bombastic guestpost, it’s authored by Baez.

Mike Stay is applying category theory to computation at a new startup called Pyrofex. And this startup has now entered a deal with RChain.”

Incidentally (but which fan reads everything?) in the same post Baez is candid about computation and category theory.

“When I first started, I thought the basic story would be obvious: people must be making up categories where the morphisms describe processes of computation.

But I soon learned I was wrong: […] the morphisms were equivalence classes of things going between data types—and this equivalence relation completely washed out the difference, between, say, a program that actually computes 237 × 419 and a program that just prints out 99303, which happens to be the answer to that problem.

In other words, the actual process of computation was not visible in the category-theoretic framework.” [boldfaced by me]

(then he goes on to say that 2-categories are needed in fact, etc.)

In Applied Category Theory at NIST (archived) we read:

“The workshop aims to bring together two distinct groups. First, category theorists interested in pursuing applications outside of the usual mathematical fields. Second, domain experts and research managers from industry, government, science and engineering who have in mind potential domain applications for categorical methods.”

and we see an animation from the post  “Correct-by-construction Casper | A Visualization for the Future of Blockchain Consensus“.


I never trusted these ideas. I had interactions with some of the actors in this story   (example) (another example), basically around distributed GLC . Between 2013-2015, instead of writing programs the fans of GLC  practically killed the distributed   GLC project  because it was all the time presented in misleading terms of agents and processes, despite my dislike. Which made me write chemlambda, so eventually that was good.

[hype] GLC and chemlambda are sort of ideal Lisp machines which you can cut in half and they still work. But you have to renounce at semantics for that, which makes this description very different from the actual Lisp machines.  [/hype]



Let’s make an invisible conference

An invisible conference is a small community of interacting scholars who assemble suddenly in a public place, acquire knowledge through experimental investigation, then quickly disperse.

UPDATE: I made a page which will be  updated with details, in time.

I made up this description by copy-paste from wikipedia flash mob and invisible college.

The definition is not complete yet, there has to be included something from a key signing party.

Before the conference.       [TBA]

During the conference.     [TBA]

After the conference.     [TBA]


In case you want to meet and talk seriously, what if we organize an invisible conference? I have to think more about the place, say Bucharest, Romania? or maybe this summer at a nice camp by the sea (you need a tent)? other idea?

Express your interest at

I put this contact also on my alternative homepage.

The “invisible” word points to the idea of an invisible college, mentioned in another post.

This post will be updated many times probably, so bookmark it because it will be less visible when other, newer posts will appear.


computing with space | open notebook

%d bloggers like this: