Quine graphs (1)

Update: here is  a page, which will be used with the article. Thank you for letting me know about any suggestions, improvements, bugs, requests. The demos will support the article and they will be grouped on families, based on subject or on common phenomena. In this article, up to now,  only chemlambda and Interaction Combinators are touched, not kali or hapax.


While hapax and anharmonic lambda calculus enter the final stage, it is time I prepare for publication the quines exploration project. I intend to make an article (first to arXiv) with a paired github repository and some github.io pages where the real things happen. For the search of new quines I might go back to twitter and make a dedicated account. Let’s see how all this will work together.

For the moment I collect here the posts from this chorasimilarity blog, or other links  which are related to the  project. (Well there is a collection of google+ posts which are going to be useful, I have to see what I do with these).

So here is it, in reverse time order:

A very useful yool was the full js chemlambda editor written by ishanpm. I modified it and tuned it in many places and I shall continue or I’ll write a new one, but definitely I learned stuff by using it, thanks!

I might explore also quines in other

although I shall not touch the relations with knot theory, in this article. Only look for quines, as example.

If you have questions, suggestions, or if you want to contribute to the subject, let me know.


6 months since my first javascript only

… program, this one: How time flows: Gutenberg time vs Internet time . Before I used js only for the latest stage, written (clumsily, I admit) by other programs. Since then I wrote hapax  and I modified other scripts to fit my needs, mainly, but this corrected a gap in my education 🙂

Oh btw if anybody interested to see/interact on this talk I’d like to propose: [adapted from a pdf (sigh) for my institution management, though they are in the process to reverse to  the pre-internet era  and they managed to nuke all mail addresses @imar.ro a domain which was  rock solid since at least 20 years; that’s why I post it here]

A kaleidoscope of graph rewrite systems in topology, metric geometry and computer science
Graph rewrite systems are used in many research domains, two among many examples are Reidemeister moves in knot theory or Interaction Combinators in computer science. However, the use of graph rewrites systems is often domain dependent. Indeed, for the knot theory example we may use the Reidemeister move in order to prove that the Kauffman bracket is a knot invariant, which means that it does not change after the graph is modified by any rewrite. In the other case given as an example, Interaction Combinators are interesting because they are Turing universal: any computation can be done with IC rewrite rules and the rewrites are seen as the computational steps which modify the graphs in a significant way.

In this talk I want to explain, for a general audience, the ocurence and relations among several important graph rewrite systems. I shall start with lambda calculus and the Church-Turing thesis, then I shall describe Lafont’ Interaction Combinators [1]. After that I shall talk about graphic lambda calculus [2], about joint work with Louis Kauffman [3] on relations with knot theory. Finally I explain how I, as a mathematician, arrived to study graph rewrites systems applications in computer science, starting from emergent algebras [4] proposed in relation with sub-riemannian geometry and ending with chemlambda [5], hapax (demo page [6], presentation slides [7]) and em-convex [8] with the associated graph rewrite system [9] (short of “kaleidoscope”).

During the talk I shall use programs which are based on graph rewrites, which are free to download and play with from public repositories.

[1] Y. Lafont, Interaction Combinators, Information and Computation 137, 1, (1997), p. 69-101

[2] M. Buliga, Graphic lambda calculus. Complex Systems 22, 4 (2013), p. 311-360

[3] M. Buliga, L.H. Kauffman, Chemlambda, Universality and Self-Multiplication, The 2019 Conference on Artificial Life 2014 NO. 26, p.490-497
[4] M. Buliga, Emergent algebras, arXiv:0907.1520

[5] M. Buliga, Chemlambda, GitHub repository (2017)
[6] M. Buliga, Hapax, (2019) demo page http://imar.ro/~mbuliga/hapax.html,
Github repository https://github.com/mbuliga/hapax

[7] M. Buliga, Artificial physics of artificial chemistries, slides (2019)

[8] M. Buliga, The em-convex rewrite system, arXiv:1807.02058

[9] M. Buliga, Anharmonic lambda calculus, or kali (2019),
demo page https://mbuliga.github.io/kali24.html


I’d like to make this much more funny than it looks by using these js scripts. Also “kaleidoscope” is tongue-in-cheek, but that’s something only we know. Anyway kali is on the way to be finished, simplified and documented. And somehow different. For a short while, encouraged by these js scripts and similar attempts, I tried to believe that maybe, just maybe there is a purely local way to do untyped lambda, right around the corner. But it seems there isn’t, although it was fun to try again to search it. But then what to do? Maybe to be honest with the subject and say that indeed a purely local system, geometry inspired, exists, it it Turing universal, but it is not lambda calculus (although it can be guided by humans into being one, so that’s not the problem)? Maybe going back to my initial goal, which was to understand space computationally, which I do now? Yeah, I know that lambda calculus is fascinating, even more if untyped,  but em is so much better!


Experimental generation of anharmonic lambda calculus (II)

UPDATE: There is still another version, less exotic, at github. Both are working versions of kali.  For those with mathematical inclinations there are explanations in the tool rhs.js. This will come to a conclusion with the explanations about FO and with the tools to choose optimal collections of rewrites.


There is a working version of kali which I posted today. Enjoy and wonder how can it (sometimes!) reduce lambda terms even if it has nothing to do with lambda calculus in the background. The js script is interesting to read, or better the script from the page which generates DIST rewrites (which you can add in your copy of the main script and play with it, it is enough to add it to the list of rewrites).

It is comical how does it fail sometimes. Space is symmetrical and logic is constrained.

Also I think I’ll pursue the idea to train the (choice of rewrites, probabilities) for certain tasks, as evoked here.

Experimental generation of anharmonic lambda calculus (I)

UPDATE: This is from yesterday 15.10.2019. It gives the possible RHS of DIST rewrites in a more precise way, compatible with the 6 nodes: A, FI, D (port 2 “in”) and L, FO, FOE (port 2 “out”) (each node has port 1 “in” and port 3 “out”). Moreover which can be decorated with generic dilations which satisfy em-convex. It turns out that there are exactly two possibilities for each rewrite. However, there are fewer than 3^36 rewrite systems which are potentially interesting, because many of these rewrites inhibit others.

For example all the rewrites used in  the working version of kali are there (with the exception of those involving the node FO, there is a separate treatment for this node; also I ignore for the moment the rewrites invoving T and I take for granted the 3 beta-like rewrites, which are not generated by the rhs.js script, because they are not DIST rewrites).The version I have today shortens the list a lot and soon enough will be merged into a more explorable version of kali.


How many rewrites are possible in anharmonic lambda and how do they relate one with the other? Is there a way to discover experimentally the best collection of rewrites? I think it is and that’s what I’m doing right now.

Let me explain.

Suppose we start by the anharmonic group, isomorphic with S(3), or why not we start with S(4), with an eye into the relation it has with projective geometry. But basically we want to associate to every element of the group (call it G) a trivalent node with named ports “1”, “2” and “3”, such that we can decorate the edges of a graph made by such nodes by “terms” which are somehow relevant with respect to the geometric nature of the group G (either S(3) as the anharmonic group, or S(4) as it appears in projective geometry). For the moment how we do that, or why are we doing it, or even what that has to do with lambda calculus are irrelevant questions.

There are two big possibilities further.

Either we work with graphs with undirected edges, but we restrict the patterns which trigger rewrites at pairs of nodes connected via the ports “3”, i.e. at pairs of nodes linked by an edge which connects the port “3” of on enode with the port “3” of the other. For example this is the case in Interaction Combinators. The advantage is that there will never be conflicting rewrites.

Or we work with graphs with directed edges, we attach orientations to ports (say ports “1” is always “in”, i.e. the orientation point to the node, the port “3” is always “out” and the port “2” may be “in” or “out”, depending on the node type) and we ask that any edge connects a port which is “in” with a port which is “out”. Then we look for patterns which trigger rewrites ahich are made by a pair of nodes linked by an edge which connects a port “3” with a port “1”. This is like in chemlambda. The advantage here is opposite: we allow conflicting rewrites.

So in either case we think about rewrites which have as LHS (left hand side) a pair of nodes, as explained, and as RHS (right hand side) either no node (actually two edges), like in the case of the beta rewrite, or 4 nodes. The pattern of 4 nodes should be like in Interaction Combinators (say like GAMMA-DELTA rewrites) or like the DIST rewrites in chemlambda.

If I take the second case, namely graphs with oriented edges, as explained. how many different rewrites are possible? More precisely, denote a node with a “+” if the port “2” is “in” and with a “-” if the port “2” is out. Then, how many rewrites from 2 nodes to 4 nodes, in the pattern DIST, are possible?

Doing it by hand is dangerous, so we better do it with a program. >We are looking for patterns of 4 nodes arranged like in DIST rewrites, each node being a “+” or a “-” node, with oriented edges, so that the 4 half edges (or external ports)  have the same orientation as the corresponding ones of the  LHS pattern made of 2 nodes (“+” or “-“). How many are they?

There are 4 cases, depending on the LHS nodes, which we denote by “+,+”, “-,-“, “+,-” and “-,+”.

I was surprised to learn from programs that theer are 386=16X23 possible RHS patterns, divided into 80=16X5, 80=16X5, 112=16X7 and 96=16X6 patterns.

While I can understand the 16X part, the 5,5,7,6 are strange to me. The 16X appears from the fact that for a node “+” we can permute the “1”,”2″ ports without changing the edges orientations, and similarly for a node “-” we can permute the “2” “3” ports with the same (lack of) effect.

Now let’s get further. We look now at the nodes which are decorated with elements of the group G, or say the group G acts somehow on the set of node types which has as many elements as G. We look for rewrites from LHS to RHS such that the decoration of the external ports does not change during the rewrites. This imposes strong restrictions on the choice of nodes (and it means something geometrically as well).

Not any possible rewrite can be accepted though. For example we reject rewrites with the property that the RHS contains a copy of the LHS. So each rewrite has associated a collection of rewrites which are inhibited by it. This will place restrictions on the collections of rewrites which we may choose for our calculus.

We reject also rewrites whose RHS contain a copy of the LHS of a rewrite we like, like the beta rewrite.

We reject rewrites which have the RHS made such that the external ports will all be “2”, because such a pattern will last forever during further rewrites.

Still when we look at what is left we see that we have about |G|X|G| LHS patterns  and much more RHS choices, so there will still be many possible calculi.

We may look for symmetries, related to the action of G on the node types and we may ask: which is the most (or a most) symmetric collection and which will be a least symmetric (but maximal in number)?

Or we may say that the human mind is feeble and let the collections compete, by reducing a family of graphs. Take lambda calculus and some tests and let the possible collections compete. Take emergent algebras and some tests and do the same. Or even look for collections more fit for certain chosen tests from lambda calculus or others.

Who will win?

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?