Tag Archives: quine

Anharmonic lambda calculus (II)

Some news after the anouncement of kali, or anharmonic lambda calculus. I use again two pages, which are updated in tandem:


At the moment I write this post the github.io version is more recent. I think the termination rewrites are better than before.

There is still some work on the exact choice of rewrites, among the many possible which are compatible with the underlying geometric structure. But you can see by looking at kali24.js that there is some connection between the nodes and the anharmonic group.

All this will be explained when I’ll arrive to the most satisfying version.

I added to the lambda calculus examples some more, not lambda calculus ones. Among them the much discussed 10-node quine and also the most amazing molecule I discovered until now. It appears in the menu as “10 nodes sometimes becomes quine from [graph A-L-FI-FOE 540213]” and please do reload it often and let it unfold. For an archived video see this one. It is a graph which basically shatters the notion that a quine is enough, conceptually, to describe life. More simply put, it can evolve in so many ways, among them in a chemlambda quine way, but not uniquely. Amazing.

You can see it also on the menu of the find a quine page. There the graphs look more compact and you can see more of the overall structure, but less the detailed linking of nodes.

Coming back to kali24, the chunk which I need to explain first is what does it have to do with em-convex. That is an enriched lambda calculus which describes my work on emergent algebras. It ends with the proof that in the presence of an axiom called “convex”,  we end up with usual vector spaces over terms of type N (in the paper) and that also the term of type N have an em calculus themselves, which is a way of saying that we recover on them a structure which is like the Riemann sphere.

What is not proved are two things: (1) is  there is a graphical rewrite system which can reproduce the proofs of em-convex, under the algorithm of rewrites used with chemlambda? (2) can we dispense of the lambda calculus part (the abstraction and application operations) and redo everything only with the pure em calculus?

Back to earth now, just for the fun, don’t you think that a geometrical model  of lambda calculus on the Riemann sphere would be nice?

The life of a 10-nodes quine, short video

I’m working on an article on the 10-nodes quine (see here and here previous posts) and I have to prepare some figures, well rather js simulations of relevant phenomena.

I thought I’ll made a screencast for this work in progress and put it in the internet archive:


UPDATE: I found, by playing, an even more, apparently, assymetrical variant of chemlambda, but also I found a bug in the js version, which is, fortunately, not manifesting in any of the cases from the menu of this page.  For the moment is not completely clear for me if the more, apparently, assymetrical variant behaves so much better, when I reduce lambda terms, because of the bug. I think not. Will tell after I fix the thing. Is something unexpected, not in my current program, but exciting, at least because either way is beneficial: I found a bug or I found a bounty.

Perturbed quine experiment

I use as a tool the page find a quine.  You saw in the post 10-node quine can duplicate that indeed in rare situations the simple 10-node quine can indeed reproduce spontaneously. You can see for yourself: choose “original 10_nodes quine” from the menu, hit the  “start” and if it dies hit “reload” and “start” until you witness a reproduction.

In this post I want to show you another phenomenon, which is logical after you see it, but perhaps is surprising at first sight.

Recall that a chemlambda quine is a graph which has a periodic evolution under the greedy algorithm of rewrites. It is of course interestign what happens under the random reduction algorithm. Maybe this definition should be changed?

What if we modify the definition by saying that a quine is a graph which can evolve into a graph which itself is a quine according to the original definition. Then, OK, but it may be the case that a graph, even one of a quine according to the original definition, has the following weird property: it can evolve into two different quines. Namely there are two different reduction paths which, each, lead to a quine.

Here is a proof that this is happening for the quine which you can load from the menu as “10 nodes quine 2 = [A-L-FI-FO 245013]”.

First, what does “= [A-L-FI-FO 245013]” means? If you look in the menu, there is the option “new random 4 nodes graph A-L-FI-FO” which generates one of the 720 graphs with 4 nodes A, L, FI, FO. Then there are some examples of such graphs which evolve into  quines, my favorite being the remarkable “quine from [graph A-L-Fi-FO 243501]”.

Then “10 nodes quine 2 = [A-L-FI-FO 245013]” means that this particular 10 nodes graph evolves into the same quine as the one which is obtained from [graph A-L-Fi-FO 245013]. So there’s one quine. (For the notation [A-L-FI-FO 245013],  notice that 245013 is a permutation of 012345 which describes in which way the nodes A, L, FI, FO are connected. You can see how is done, and especially why there are 720 such graph, if you look in the molLib.js at the lines after

case random_egg_A_L_FI_FO


The second quine can be obtained by a perturbation. Indeed choose “10 nodes quine 2 = [A-L-FI-FO 245013]” from the menu and start to perturb it with the mouse:


Then press “start”


That’s a different quine. Indeed, most of the time you get the first one which is small:


You can see it by doind simply “reload” and “start”.

Only rarely you’ll see the bigger quine.

Other surprises wait for you, and for me too.




Lafont’ quine online

UPDATE: Now you can search for Interaction Combinators quines among those generated by random 4 nodes (2 GAMMA, 2 DELTA). They are all immortal, because there are no conflicts in IC. They seem to be not so rare, I quickly discovered 6. Also, because the IC rewrites have so many symmetries, they are less varied than chemlambda quines generated from 4 nodes graphs.


I discovered that ishanpm js version of chemlambda does not give a darn on arrow orientations. So I added Interaction Combinators rewrites and nodes and now you can see online Lafont’ quine 🙂



So after you choose “Lafont’ quine” from the menu, hit “load” and then you can either hover with the mouse to trigger rewrites, or you can move the point or view and scale the graph with the mouse, or you use “step” to make 1 rewrite step, or “start” and “stop” to let the program do it.

It is interesting that this is possible and it is done by cleverly exploiting the mol file notation. Indeed, in this js version Ishan baptizes the ports by

“left” , “out”, “right”

for any of the 3-valent nodes, and the information about nodes types (L, A, FI, FO, FOE) and ports through which are connected  it is sufficient to unambiguously identify the chemlambda rewrites.

That means the script does not care if you put (in the molLib.js) an incorrect mol file (see here for the correct mol notation in chemlambda and hapax). It is sufficient that it executes correctly the chemlambda rewrites.

However this leaves some room. I added nodes types GAMMA and DELTA, which are 3-valent, with the ports “left”, “out”, “right” of type “0” (that means “in”, but who cares if this is never used later?). I use the node “T” from chemlambda as the node “EPSILON” from IC.

So the node with notation:

GAMMA 1 2 3

represents a gamma node in IC, with the principal port 1, and other ports 2 and 3. Same for DELTA.

A GAMMA-GAMMA rewrite is therefore, in mol notation terms, a transformation of the pattern:

GAMMA 1 2 3

GAMMA 1 4 5

into a pattern

Arrow 3 4

Arrow 2 5

What’s funny is that Ishan does not use Arrow rewrites either, because he executes at one time step only one rewrite, at random, so that means that instead a GAMMA-GAMMA rewrite as written before transforms into an empty pattern and a gluing of the remaining halves of the edges 2, 3, 4, 5 such that 3=4 and 2=5.

And so on.

So you have for the first time the Lafont’ quine online and don’t forget about the other quines discovered in chemlambda just by randomly shuffling of sources and targets of the 10_node chemlambda quine.


10-node quine can duplicate

Only recently I became aware that sometimes the 10-node quine duplicates. Here is a screenshot, at real speed, of one such duplication.


You can see for yourself by playing find-the-quine, either here or here.

Pick from the menu “10_nodes quine” or “original 10 nodes quine” (depending on where you play the game), then use “start”. When the quine dies just hit the “reload” button. From time to time you’ll see that it duplicates.  Most of times this quine is short lived, sometimes it lives long enough to make you want to hit “reload” before it dies.



Find the quine: who ordered this?

I put a version of the Find the Quine on github. You may help (and have fun) to find new chemlambda quines.

The page lets you generate random 10 nodes graphs (molecules), which are variants of a graph called “10_quine”. There are more than 9 billion different variants, therefore the space of all possibilities is vast.

Up to the moment 15 new quines candidates were found. You can see them in that page too.

New phenomena were discovered, to the point that now I believe that chemlambda quines are a dot in a sea of “who ordered this?”.

Who ordered this? Just look at “new quine? 3”.  “10 nodes quine 5”. It displays an amazing range of outcomes. One of them is that it dies fast, but other appear rather frequently. The graph just blooms not into a living creature, more like into a whole ecology.

You can see several interesting pieces there.

There is a “growing blue tip” which keeps the graph alive.

There are “red spiders” who try to reach for the growing blue tip and eat it. But the red spiders sometimes return to the rest of the graph and rearrange it. They live and die.

There is a “blue wave” which helps the growing blue tip by fattening it.

There is a “bones structure” which appears while the red spiders try to eat the growing blue tip. It looks like the bones structure is dead, except that sometimes the red spiders travel back and modify the bones into new structures.

And there are also graphs which clearly are not quines, but they are extremely sensitive to the order of rewrites. See for example “!quine, sensitive 1”. There seems to be a boundary between the small realm of quines and the rest of the graphs. “new quine? 3” is on one side of that boundary and “!quine, sensitive 1” is on the other side.

So, play “Find the Quine” and mail me if you find something interesting!

On top of the page there is a link to my pages to play and learn. Mind that the versions of find the quine there and at github are slightly different, because I update them all the time and so they are not synchronized. I use github in order to have a copy just in case. In some places I can update the github pages, in other places I can update my homepage…



What is a chemlambda quine?

UPDATE 3: I made a landing page for my pages to play and learn.

UPDATE 2: And now there is Fractalize!

UPDATE: The most recent addition to the material mentioned in the post is Find a Quine, which let you generate random 10 nodes graphs (there are 9 billion of them) and to search for new quines. They are rare, but today I found 3 (two all of them are shown as examples).  If you find one, mail me the code (instructions on the page).


The ease of use of the recently written chemlambda.js makes easier the sharing of past ideas (from the chemlambda collection) and as well of new ideas.

Here is some material and some new thoughts. Before this, just recall that the *new* work is in hapax. See what chemlambda has to do with hapax, especially towards the end.

A video tutorial about how to use the rest of new demos.

The story of the first chemlambda quine, deduced from the predecessor of a Church number. Especially funny is that this time you are not watching an animation, it happens in front of you 🙂

More quines and random eggs, if you want to go further in the subject of chemlambda quines.  The eggs are 4-nodes graphs (there are 720 of them). They manifest an amazing variety of behaviour. I think that the most interesting is that there are quines and there are also graphs which have a reversible evolution, without being quines. Indeed, in chemlambda a quine is one which has a periodic evolution (thus is reversible) under the greedy algorithm of rewrites. But there is also the reversible, but not quine case, where you can reverse the evolution of a graph by picking a sequence of rewrites.

Finally, if you want to look also at famous animations, you have the feed the quine. This contains some quines but also some other graphs which featured in the chemlambda collection.

Most of all, come back to see more, because I’m going to update and update…