Tag Archives: quine graphs

16 animations which supplement arXiv:2005.06060

Here is a list of 16 animations (which you can play with!) which supplement well the article

Artificial life properties of directed interaction combinators vs. chemlambda

and it’s associated page of experiments.


From the page of experiments you can travel to other directions, too!

Alife properties of directed interaction combinators vs. chemlambda

UPDATE: see arXiv:2005.06060.

The chemlambda project has a new page:

Alife properties of directed interaction combinators vs. chemlambda

This page allows experiments with graph quines under two artificial chemistries: directed interaction combinators and chemlambda. The main conclusion of these experiments is that graph rewrites systems which allow conflicting rewrites are better than those which don’t, as concerns their artificial life properties. This is in contradiction with the search for good graph rewrite systems for decentralized computing, where non-conflicting graph rewrite systems are historically preferred. Therefore we propose conflicting graph rewrite systems and a very simple algorithm of rewrite as a model for molecular computers.

Here we compare two graph rewrites systems. The first is chemlambda. The second is Directed Interaction Combinators, which has a double origin. In Lafont’ Interaction Combinators is also described a directed version. We used this proposal to provide a parsing from IC to chemlambda,



which works well if essentially one chemlambda rewrite is modified. Indeed, we replace the chemlambda A-FOE rewrite by a FI-A rewrite (which is among Asperti’ BOHM machine graph rewrites). Also some termination rewrites have to be modified.

For the purposes of this work, the main difference between these two graph rewrite systems is that chemlambda has conflicting rewrite (patterns) and Directed IC does not have such patterns. The cause of this difference is that some chemlambda nodes have two active ports while all Directed IC nodes (as the original IC nodes) have only one active port.


Biological immortality and probabilities of chemical rewrites

This post is a continuation of the post Random choices vs older first. There is an apparent paradox involving the probability to die and the probability of a chemical rewrite.

An organism is biologically immortal if its probability to die does not depend on its age. Another probability which matters for organisms made of chemical compounds is the probability of a chemical rewrite, say relevant for the organism metabolism.

Let’s suppose that there is a mechanism for such a chemical rewrite. For example, for each rewrite there is an enzyme which trigger it, like we supposed in the case of the chemical concrete machine. We can imagine two hypothetical situations.

Situation 1. The organism is chemically stable, so in the neighbourhood of a rewrite pattern there is a constant in time chance of the presence of a rewrite enzyme.  The probability of the chemical rewrite would be then independent on time. We would expect, for example, that biologically immortal organisms are in this situation.

Situation 2. There is a more complex mechanism for chemical rewritesm where there is a way to make a probability of a chemical rewrite to depend on time. As an example, suppose that the presence of the rewrite pattern triggers the production of rewrite enzymes. This would make the probability of the rewrite to be bigger for older rewrite patterns. But if probabilities of older rewrite patterns to be transformed is bigger than the probabilities of newer rewrite patterns, that would imply that the general probability to die (no more rewrites available) would be time dependent. It seems that such organisms are not likely to be biologically immortal.

The paradox is that it may be the other way around. Biologically immortal organisms may be in situation 2 and mortal organisms in situation 1.

This is illustrated by chemlambda quines. The page How to test a quine allows to change the probability of the rewrites with respect to time.

By definition a quine graph is one with a periodic evolution under the greedy algorithm of rewrites, which performs as many non-conflicting rewrites as possible in a single step. The definition can be refined by adding that in case of conflicting rewrites the algorithm will choose a rewrite which “grows” the graoh, by increasing the number of nodes.  What is interesting is how such a quine graph behaves under the random rewrites algorithm.

A graph reduced with this greedy algorithm evolves as if it is in the extreme of the Situation 2, where older rewrite patterns are always executed first (maybe excepting a class of rewrites which are alway executed first, like the “COMB” rewrites). This observation leads us to redefine a quine graph as a graph which is biologically immortal in situation 2!

You can check for yourself that the various graphs (from chemlambda or Interaction combinators) from that page are indeed quine graphs. Do like this: pick a graph from the menu. Move the “rewrites weights slider” to the “grow side”. Click on the “change” button to have the message “older is first”. Click “start”. If you want to reload then click “reload”.

A quine graph is an example of an (artificial life) organism which is immortal if the rewrites probabilities depends on the age of the rewrite pattern.

Under the random rewrite algorithm , i.e. Situation 1, such a graph quine may die or it may reproduce. They are indeed alive.


Random choices vs older first

There is now a page to check if a graph is a quine. This is done by a clarification of the notion of a quine graph.

The initial definition for a quine graph is: one which has a periodic evolution under the greedy algorithm of rewrites. The greedy algorithm performs at each step the maximal number of non-conflicting rewrites.

Mind that for some graphs, at one moment there might be more than one maximal collections of non-conflicting rewrites. Therefore the greedy algorithm is not deterministic, but almost.

In the js simulations there is performed one graph rewrite at each step, so how can we modify this to be able rto check if a graph is a quine?

The answer is to introduce an age of the nodes and links of the graph. There is an age (global) counter which counts the number of steps. Each new node and each new edge receive an “age” field which keeps the age of the birth of the said node or link.

The age of a rewrite pattern is then the maximum of ages of it’s nodes and links.

The “random choices” lets the initial reduction algorithm as is. That means the rewrites are executed randomly, with the exception of “COMB” rewrites which are always executed first.

The “older is first” executes always the rewrites on the oldest rewrite patterns (with the exception of “COMB” rewrites which are executed first, when available. The effect is that the algorithm reduces sequentially maximal collections of non-conflicting graph rewrites!

Therefore the definition of a quine graph should be modified to: a graph which has bounded (number of nodes and links) evolution under the “older is first” algorithm.

It is however intriguing the stabilising effect of “older is first”. Just look at the 9_quine, with the “older is first” it never dies, as expected, but under  “random choices” it does.

Similarly, use the new page to look at the behaviour of the 10_nodes quine. It either dies immediately or it never dies. This is understandable from the definition, because this quine has either a maximal collection of rewrites which kills it or another maximal collection of rewrites which transforms it into a graph which ahs periodic evolution from that point.

But what is intriguing is the suggestion that there should be a tunable parameter, between “random choices” and “older is first”, namely a parameter in the probablility of the rewrites which decrease with age (i.e. older patterns are more probable to be rewritten than the newer ones). At one extreme older patterns are always executed first. At the other extreme there is the same probability no matter the age of the pattern.

To have probabilities strongly depending on the age of the pattern stabilize the evolution of a quine graph: it may die quick or it lives forever. Probably it does not reproduce.

On the other side, a lower dependence on age implies a more natural evolution: the quine may now die or reproduce.

Quine graphs (5), anharmonic logic and a flute

Several things:

  • added a new control to the quine graphs pages (all can be accessed from here). Is caled the “rewrites weights slider”: you can either favor the rewrites DIST, which add nodes to the graph, or the rewrites β  which take away nodes from the graph (for chemlambda these are the L-A rewrite, but also the termination rewrites and FI-FOE). This changes, sometimes radically, the result of the algorithm. It depends what you want. In the case of reductions of lambda terms, you may want to privilege β rewrites, but as usual this is not generally true, see the last example. In the case of the fight arena for quines, you can favor a species of quines over another by your choice.
  • of course in the background I continue with kali, or anharmonic lambda calculus. The new thing is that why not conceive a programming language which compiles to kali? It works fine, you can say things as

“from a see b as c” or

“let a mark b as c” or

“is a as b” or

“c := let x  = b in c”

and many others! Soon, hope at the beginning of December, will be available.

  • It helps to do new things, so I finished t day my first flute. Claudia, my wife, is a music professor and her instrument of choice is the flute. From a physics point of view a flute is a tube with holes placed in the right possitions, how hard would it be to make one? After I made it, it is usable but I started to learn a lot of stuff about how unnatural is the modern flute and how much you can play with all variables. As a mathematician I  oscilate between “is a known thing to simulate a flute numerically” and “I shall concentrate on the craft and will play with various techniques”. My first flute was a craft only effort, but now, when I know more, I am hooked!

OK, so that’s the news, I like to make things!


A small ouroboros has a short life (Quine graphs 4)

As I said many times, there is a lot of background to the hundreds of chemlambda mol files and associated simulations. Now that I took the Quine graphs repository seriously, I have to select rather clear and short strings of facts associated to the mol files, so that I can tell clear and short enough stories.

So it came out of the depth of this pile of stuff I have that the ouroboros is not an immortal quine. It can die and his life is of the order exp(length) where length is the length of the double track it contains.  The shortest ouroboros appears here (look in the MENU).

Otherwise, I reorganize (and continue to do so) the js scripts, so that they become easy to understand. Now there is a chemistry, nodes, etc. so thare will be a convergence with the modules of hapax.

Quine graphs (3), ouroboros, hapax and going public

Several news:

I decided that progressively I’m going to go public, with a combination of arXiv, Github and Zenodo (or Figshare), and publication. But there is a lot of stuff I have to publish and that is why this will happen progressively. Which means it will be nice to watch because it is interesting, for me at least,  to answer to the question:

What the … does a researcher when publishing? What is this for? Why?

Seriously, the questions are not at all directed against classical publication, nor are they biased versus OA. When you publish serially, like a researcher, you often tell again and again a story which evolves in time. To make a comparison, it is like a sequence of frames in a movie.

Only that it is not as simple. It is not quite like a sequence of frames,  is like a sequence of pictures, each one with it’s repeating tags, again and again.

Not at all compressed. And not at all like an evolving repository of programs which get better with time.

Quine graphs (2)

UPDATE: This page has now comments for each graph  , or its sister page. Now I can start to mass produce 🙂

There are several technical details to add before I arrive to a final version, but now there are, as usual, two sister pages:

  • (the one I want to write about today) here
  • and the one at the quinegraph repository here (link changed, mentioned in the last post)

The first page, ie the newer one, has the algorithm involving the COMB rewrites and Arrow nodes, even for Interaction Combinators, which is part of the original chemlambda programs.  It may be funny to see the Arrows and COMB rewrites in action in the case of IC.

This part is needed because the way a graph quine is defined. The Arrow and COMB rewrites allow to make purely local parallel rewrites. For the case of Interaction Combinators, where the graphs are not oriented, a hack can be done in order to use Arrows, which consists into using a pair of them, tip to tip, instead of only one. (Not the first time when I think that IC is bosonic and chemlambda is fermionic 🙂 )

That being said, what more is needed?

  • to fully implement the greedy algorithm, because only the sequential random one is in the js version (let’s recall again that the js-only version was first done by ishanpm, then modified by me according to (many) needs. It is a marvel, even if it needs more tweaks, in particular from my point of view because by using it I discovered that the 10 quine can reproduce itself). Needed because of the definition of a quine.
  • to put a graph matching function. There is one in the more ambitious project hapax. (It does not have pretty pictures, but I’ll modify it after, maybe that is why it does not attract?) Useful for the verification of a quine.
  • depending on time, implement a sort of arena where quines compete. Needed for a part of the article (or maybe a supplement?) where I explain some things mentioned in the deleted g+ chemlambda collection (adaptation is another semantic ilusion)
  • finally I need to arrive to a not too primitive form of html presentation, these days people are used to such things and the academic who just want to show a proof of principle will be ignored without. Needed because it can be done and is good for my education.

All in all, ironically, my initial awk program (4364 sloc) does that and more (Turing machines, to come in js version, as well as Formality Core) in so many lines because perhaps they were needed? I say ironically because that program is written without the use of functions, so perhaps it is about 1000 sloc with functions. Compare with the js version which has the same number of lines, written by ishanpm. Compare with the Haskell version written by synergistics,  Compare with the python version by 4lhc.

Most of these lines are needed to destroy the information added to the system by the semantic assumptions of those who wrote the programming languages. Yes.

I close here by saying that even if I don’t believe in semantics, as it is understood since Aristotle (but not by Plato), I do believe in the existence of a different, more beautiful replacement, which can be glimpsed in the way nature needs randomness for creating structure.


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.