provided that we renounce at the chemlambda rewrites A-FO and A-FOE

and we replace them by a rewrite FI-A.

Some termination rewrites are modified as well. More precisely, these termination rewrites from chemlambda v2 are eliminated: and replaced by these different termination rewrites: The chemistries are described in the file chemistry.js. Chemlambda rewrites are obtained by concatenation of "CHEMLAMBDABARE" with "CHEMLAMBDAEND" and dirIC rewrites are obtained from concatenation of "CHEMLAMBDABARE" with "DICMOD". General pure termination rewrites "T" and the "COMB" rewrites which manage the Arrow nodes are part of both chemistries. The resulting graph rewrite system is very close to Asperti' BOHM machine graph rewrite system.

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


1st hypothesis: these rewrites can also be used to make real molecular computers.

2nd hypothesis: the enzymes create a graph rewriting algorithm which can be implemented by local machines.

Here a local machine is a defined as a Turing machine with two tapes: the IO tape and the work tape. Molecules are encoded as mol patterns, which are vectors of mol nodes, where each mol node is a vector of node types and tags of edges connected to the node ports. The tapes of the machine have cells, each cell of a tape can contain a node type, a port type, an edge tag or a finite set of special characters.

The machine can read from on the IO tape a cell, write a whole mol node at the end of the mol pattern, or delete a whole mol node. For each read/write or delete from/to the IO tape the machine writes the same on the work tape. The machine can read from the work tape and it can write only on the blank cells of the work tape. The machine can either halt (by writing a halt symbol on the work tape) or it can delete the whole work tape and then the IO head jumps to a random mol node beginning.

The constraints are:

- the machine can perform any graph rewrite on any molecule
- at each moment the IO tape contains only a well written mol pattern
- the work tape has finite length.

A graph rewriting algorithm which can be implemented by a local machine is by definition local in space, in the sense that the graph rewrites can be performed by using a local machine (therefore by a TM with a finite work tape), and local in time, in the sense that the algorithm can retain only a limited in time portion of the history of the graph evolution.

In these simulations we use a random rewrite algorithm and we also randomize as many times as necessary the data (mol file, list of possible rewrites,...) in order to destroy all information which cannot be processed by a local machine. As an example, the list of nodes in the mol file is ordered, but we have to avoid this information and instead to jump randomly to a node or explore from a node only a limited portion of the graph. The only exception we make is to be able to use an age of the node or of the link of the graphs, for the purpose of searching for quine graphs (see below about the use of the "change" button for the "older is first" option). We could, instead use a local algorithm based on age, where there is a upper age parameter such that the age of a node or link which is bigger than the upper age trigger an age reset (and also it may trigger a rewrite, like deletion of the old node or link). However, in these experiments we don't go in this direction.

Problem: find those graph rewrite systems which admit artificial life, i.e. graphs (molecules) with the properties

- they have metabolism (graph quines)
- they can duplicate
- they can die.

Here a graph quine is a molecule which admits a periodic evolution under graph rewrites, provided the local machine is constrained to rewrite older graph rewrites patterns first and to choose one among the possible strategies: whenever possible to prefer the rewrites which grow the number of nodes ("GROW") vs those which reduce the number of nodes ("SLIM") or inversely.

Once we have a graph quine, we are interested if such a molecule can duplicate or die if the local machine is not constrained by the age of the rewrites patterns or by the choice of a strategy.

Comment: this definition of metabolism is very low level. Indeed, according to it, the citric acid cycle defines a graph quine. [image source: wikipedia]

Death of a quine graph is understood as the evolution to a state where no more graph rewrites are possible.

We see in these experiments that the choice of the graph rewrite system is important if we want to have graphs with these artificial life properties.

We can experiment with 10 chemlambda quines and with 5 Interaction Combinators quines, on the same ground. There are comments relevant for each quine, which appear when the user chooses a quine from the menu. We use a list of quines which contain those initially presented in
[IC & chemlambda quines. Marius Buliga (2019-2020), https://mbuliga.github.io/quinegraphs/ice.html#howto].
For a graphically more lively, with more examples, but with less explanations page, see the older
[Find a quine. Marius Buliga (2019), https://mbuliga.github.io/find-the-quine.html]

There are examples which show that:

- a chemlambda quine may be as big as we wish (the "ouroboros quine"). This is the first discovered chemlambda quine, from the graphical reduction of the predecessor of a Church number, as explained in
[The Ouroboros. Marius Buliga (2019-2020), https://mbuliga.github.io/quinegraphs/ouroboros.html#howto]
- some chemlambda quines can duplicate (the 10_nodes quine),
- there exist non-connected quines (the 16_quine_A_L_FI-FO) which are not made by connected components which are quines,
- birth of quines (16_quine_A_L_FI_FO_duplicate), see also this first string of demos
[The birth and metabolism of a chemlambda quine. Marius Buliga (chorasimilarity) 2015,http://chorasimilarity.github.io/chemlambda-gui/dynamic/A_L_eggshell.html
- there exist chemlambda graphs which can evolve into two different quine graphs (nature vs. nurture),
- quines can be combined into bigger quines, by "hybridization", see here hybrids and the first explanation in the commented animation
[How big an artificial living molecule can be? Chemlambda collection of animations. Marius Buliga (2017-2020), https://chemlambda.github.io/collection.html#4]

IC quines are given as well, starting with Lafont' quine, which appears in the foundational article about interaction combinators, and continuing with IC quines discovered from random search in a big family of IC graphs.

There are also options to search for new quines among random graphs.

For the IC quines we can transform them into dirIC graphs, which have nodes compatible with chemlambda. For any of these quines we can see their evolution under chemlambda or under dirIC.

In order to verify if a graph is a quine we need to do the following, as described in
[How to test a quine. Marius Buliga (2019-2020), https://mbuliga.github.io/quinegraphs/quinegraph.html#howtoquine]:

- click on the first "change" button on the left to see the message "older is first".
- choose among the two extremal strategies "GROW" or "SLIM" by moving the rewrites weights slider. For chemlambda or IC quines the choice is "GROW".
- choose among the chemistries dirIC or chemlambda by using the second "change" buton.

If the evolution of the graph is periodic then we have a quine.

These quines have a metabolism, in the following sense. We use the first "change" button in order to have "random choices" and we move the rewrites weights slider to the middle (or we can position it as we like in different experiments, or even during the evolution of the graph). We are now in the random rewrites algorithm. A graph (in particular a quine graph) exhibits metabolism if it has an approximately periodic evolution for an ammount of time, followed perhaps by death. Death is lack of rewrites available.

Use the third "change" button to move from "colored nodes" to "uncolored nodes", to see how the new nodes replace the old nodes of the graph. If we are set on "uncolored nodes" then all the new nodes will have the same color. When you click again on the third "change" button, you see the text "colored nodes" and the effect is that the new nodes will have the standard (different according to their type) colors.

We see that chemlambda quines as well as dirIC quines exhibit metabolism, but only chemlambda quines may die. The lack of conflicting rewrite patterns induces a unique final state of a graph, when it exists, which is a desired property in distributed computing. The same unicity is not desired in artificial life.

We achieved replication in chemlambda but not in dirIC, probably due to a lack of enough experiments.

A curious phenomenon is that some IC quines do not translate to dirIC quines. This is due to the fact that the translation from IC to dirIC works as expected for graph which have a final state where there is no possible reduction left. In the case of an IC quine, the reduction does not terminate, it is periodic. When translated to a dirIC graph we know that the reduction can't terminate, but there is no guarantee that the reduction is periodic. We only know that if we synchronize the rewrites (so as to respect the fact that a rewrite in IC is two rewrites in dirIC) then we shall have a periodic evolution.

Some chemlambda quines are dirIC quines as well and inversely. But more times (as shown by experiments) a chemlambda quine dies fast in the process of quine checking (i.e. "GROW" strategy and "older is first"). Namely this happens for chemlambda quines which can die (attain a final state) under the rewrites from CHEMLAMBDABARE.

Finally, if we want to explore the computational properties of these chemistries, see
[Lambda calculus to chemlambda. Marius Buliga (2019-2020), https://mbuliga.github.io/quinegraphs/lambda2mol.html#lambdanote],
which is a parser and reducer which has the option to choose the chemistry for reduction of lambda calculus terms. Under this simple rewriting algorithm, chemlambda is better than dirIC, but nevertheless the dirIC has many cases where it reduces lambda terms as well.