How to visualize artificial molecules in chemlambda

UPDATE:  I’ve updated the explanations page, where you can download a new variant of the formalism, which eliminated the CO-COMM and CO-ASSOC moves by the introduction of a new FO node (called “FOE”), something inspired from the analogy with DNA-RNA:

• there were 4 main nodes in chemlambda, A, L, FI and FO, and there are 4 nucleotides in DNA,  namely G,A,C,T
• in the new version appears a new node, like in RNA which uses three of the DNA nucleotides G,A,C and a new one, U.

In this new version of chemlambda appear two new dist moves, DIST-FI and DIST-FO, as well as modifications of FAN-IN and the old DIST moves which use in some places the FOE node instead of FO.

See it in action in the example on the correct self-multiplication of the S combinator, where the FOE node is yellow.

I am preparing  a click and play tutorial on that.

You can go already to the gallery of examples.  Look at them and play with the nice graphs!

But you can already play with the stuff which makes the graphs!

I shall explain in a moment how to do this. Before that I write a very short description of what is this all about.

Chemlambda  is an artificial chemistry like the Alchemy of Fontana and Buss but with rather big differences. They (Fontana and Buss) say basically that http://fontana.med.harvard.edu/www/Documents/WF/Papers/objects.pdf

• a  molecule is a lambda term in normal form, and a (chemical)  reaction between  molecules A and B is the term AB obtained by using the application operation,  followed then by evaluation (ie reduction to normal form). They don’t get far enough with this so they import
  the notion of type, which would limit the possible reactions. For some reason they identify the  molecule’s  behaviour with the function associated to the lambda term (which implies of course that one has to assume eta reduction)
•  in contradistinction, in  chemlambda  a molecule is a graph made by graphical elements called atoms. The  application and abstraction (operations from lambda calculus)  are just atoms, along with the fanout and the fanin atoms.  Some molecules  are associated (represent)  lambda terms. Some others are not.  Chemical reaction  means  reduction, dome by local graph rewrites (one reduction per chemical reaction). More specifically, each reduction move is seen as a manifestation of a chemical reaction between a molecule and an invisible enzyme specific to the type of reduction (there is a beta enzyme for example).
  There is no identification between a molecule and it’s function.

The dream is the same, though,  namely that if not all chemistry, maybe some parts of organic chemistry are used in real life like that, and not like in the bits-and-boolean-expressions- run-by-a-TM-automaton-model.

There is no need for seeing these graphs (molecules) in the plane or in 3D space (well, in 3D they embed anyways, and  maybe there are real chemicals which behave like this!) because graphs don’t need to be embedded somewhere to make sense. In particular, these graphs are not constrained to be planar.

_______________________________________

How to play with the visualizer for chemlambda already. Follow these steps:

• download http://imar.ro/~mbuliga/play.tar.gz
  and you put it in a folder,
• open a terminal window and typegunzip play.tar.gztar xvf play.tarthen you have all you need.
• now you can play, type

bash main_viral.sh

and look what happens. You’ll be asked to choose a something.mol file. There are several in the tar.

• then open the file look.html  with your favourite browser (with javascript enabled) to see the results.

You can play without being connected to the net.

The input files are called something.mol . I put in the archive some examples. You can write new ones like this. For this you have to read the post about the g-patterns notation.

In a something.mol  file there is a list in plain text (with space as separator character in the line and \n as separator character between lines). Is the list of the graphical elements of the g-pattern, but with the [ , ] deleted.

Thus instead of writing A[1,2,3] FO[3,4,5] you write

A 1 2 3

FO 3 4 5

Say you write a new .mol file, which is called blabla.mol. Save it  and then  type

bash main_viral.mol

There will be a text which appears which asks you to choose a mol file. You type blabla.mol and you hit enter. then you look with look.html, as explained.

For more explanations what it does, just open in a text editor the file check_and_balance*  and read there.  There are explanations inside.

If you look in the folder you see the appearance of several files with names starting with temp_* Open them to discover answers to some questions you may have.

For the moment, there is really no replacement for reading the chemlambda formalism. No chit-chat will suffice, I tell you from experience.

That is why, although I look for creative and open people to discuss it, I shall not engage in any meaningless stuff.

If you are creative yourself then you’ll understand and you shall not think the following applies to you.

OK, here goes the other part of the post.

I shall ignore naive questions (because I saw that most of the naive questions come from people who don’t like to really understand, so probably they won’t read my answers). Moreover, I shall not respond to any question which contains the word “bot”, because WTF is a bot anyway and what that has to do with more than a hundred posts about chemlambda and several articles? Nothing at all!  You want “bots” then don’t waste my time.

However…

-before asking the next most stupid question, let me answer: no man, the graphs are not processes. No! No chance! No, it’s not related to categories. No, it’s not ZX. No, has nothing to do with spiders, quantum diagrams and all this stuff, you know why? because these graphs don’t represent processes.

– if you don’t know what a graph is or if you deeply feel that a graph has to be embedded in some external physical space, then refresh your reading of the definition of a graph. As well you may go and read this post.

– if you don’t know what a graph rewrite is then  google it.

– if you don’t know what “local move” or “local graph rewrite” is it surely mean that you have not read anything about chemlambda, but here is the answer: a N-local move which consists into replacing   at most N nodes and edges. All moves of chemlambda are at most 10-local.

-if you don’t know what is the reducton strategy used, then congrats, that’s the first intelligent question. For the moment, the strategy of reduction is the most stupid one (I call it like this, but it is brilliant compared to others), described here

Reduction strategy. For the moment I am using a sequential strategy of reduction, with priority choices, like this:

At each reduction step do the following:

• if no LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR are present in the g-pattern, then stop, else
• identify the LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
• apply the moves from LEFT to RIGHT
• apply the COMB moves until no Arrow element
  can be eliminated
• repeat.

The priority choice is called “viral”, meaning that DIST > BETA>LOC PRUNING.

For the moment the moves CO-COMM and CO-ASSOC are not used.

This is not yet distributed GLC, there is a ladder of other strategies to explore. I personally think that they are not a big deal, but I see from experience that this is not obvious. Moreover it is very entertaining to see these strategies in action, all this gives me the occasion to learn new tricks, so in the future I shall add new strategies.

_________________________________

Tell me what you think, and most recommended is to play with it first.

____________________________________

You can play with the priority choice “viral”

UPDATE: go to the page the y combinator in chemlambda to see visualizations of chemlambda molecules and their reductions.

If you want to make your own then go to the explanations page and download and follow the instructions.

There is a gallery of examples now!

UPDATE 2: …phew, the fact that the shell script which launches the gui  is called “main_viral.sh” is related to the reduction strategy used, has definitely nothing to do with the shellstock vulnerability.

 

___________________________________

You can download  the awk file

check_and_balance_18_09.awk

and play with chemlambda with the priority choice “viral”. [see the UPDATE!]

This priority choice privileges the moves which increase the number of nodes in favour of those which decrease it.

More concretely DIST>BETA>LOC-PR. It is one of the priority choices from the post When priority matters.

How to use it:

• a g-pattern (or molecule)  is in file.mol, as a list of graphical elements (i.e. nodes with ports), but with the characters “[”    “,” and “]” replaced by spaces ” “. That means T[a] appears as “T a”, Arrow[a,b] appears as “Arrow a b” and L[a,b,c] appears as “L a b c”.

Look at data_8.mol , which is the file for the initial pattern from the post When priority matters. Here is also data_7.mol, which is the file containing the initial pattern from the post When priority does not matter.

• Download the check_and_balance_18_09.awk . Download one of the data_7.mol or data_8.mol, or create your own mol file.
• open a terminal  (presuming you have linux, or mac with Xcode installed, I suppose) and type

awk -f check_and_balance.awk data_7.mol

to play with data_7.mol. Then type ls to find a number of files, each one starting with “temp_”.

The file temp_nodes_before is basically the same as the input file.

The file temp_proposed_moves has the proposed moves 🙂 , before any priority choice and before any COMB moves.

The file temp_final_nodes has the result after one reduction step.

You may remark the apparition of new nodes, like

FRIN 17

which is a “invisible” node which has only one port (in this case named “17”) which is an “out” port. It signals that port 17  is free (and it appears as a free “in” port, that is why FRIN, which caps it, has to have a paired “out” port).

FROUT 0

which is a invisible node with only one port (named “0” in this case) which is a “in” port. For similar reasons as before, it signals that 0 is a free “out” port.

This may change slightly the aspect of g-patterns, in the only sense that arrow elements with both ends free are replaced by  pairs FRIN and FROUT, for example if

Arrow[ 17 , 0 ]

has both ports free, you shall see it in the temp_final_nodes as

FRIN 17

FROUT 0

Otherwise the FRIN-FROUT thing helps the understanding, in the sense that it makes visible the free ports.

• if you want to go further with the reduction then type

awk -f  check_and_balance.awk  temp_final_nodes

and look again at

temp_nodes_before   to see where you start in this reduction step

temp_proposed_moves to see the new moves proposed  before any priority choice

temp_final_nodes  to see the result.

And so on and so forth.

If you use data_7.mol or data_8.mol (or any  g-pattern from this blog which is reduced by the “viral” priority choice) then you should see exactly what is described in the respective posts.

There is a small trick, namely that when DIST moves are done, the script has a way to choose new names for the new edges which appear. The trick is that first it computes the max over existing port names ( that is the variable “tutext”) and then it baptizes the new ports with   tutext concatenated with “a”, tutext concatenated with “b”,  with “c” and with “d”.   This way one can be sure that the new ports don’t have names which conflict with the old ports.

I don’t have yet a visualizer for this, but work (mostly to understand) to use d3 for this.

UPDATE (20.09.2014):  I can see my first molecule during reduction, basically using this and the json file produced by the script.

it  represents (Lx.y) Omega, where Omega= (Lx.xx) (Lx.xx) ).

I can move and play with it but I have to control the colors, the ports, oriented edges. Soon.

Enjoy! Criticize! Contribute!

_____________________________________________________________

 

 

How space is born (0)

This opens a new series of posts, which will turn us back to the “computing with space” theme, the main interest here at chorasimilarity.

Look again at the move R2 of graphic lambda calculus.

 

The epsilon and mu are, originally, elements of a commutative group. Suggestions have been made repeatedly that the commutative group can be anything.

The epsilon and mu are port names, just like the red 1, 2, 3 from the figure.

In the more recent drawing conventions (not that that matters for the formalism) the port names are in blue.

Here is again the same move, but without the epsilon and mu.

Of course, the green node is the fanout, in the chemlambda version.

Yes, eventually, everything is related to everything in this open notebook.

In the next posts I shall take it step by step.

________________________________________________________________

 

 

 

 

 

 

 

 

Gold OA with CC licence, Green OA without and a lesson from the dispute between Amazon and Hachette

Further are some data along with my speculations, which may be or may be not accurate, due to my limited understanding.

Hey, everybody has a limited understanding, here is mine!

TL;DR> The crux of the matter is in this part of  any recent CC 4.0 licence: in Section 2/Scope/a. Licence grant/5.

• “5. Downstream recipients.
  1. Offer from the Licensor – Licensed Material. Every recipient of the Licensed Material automatically receives an offer from the Licensor to exercise the Licensed Rights under the terms and conditions of this Public License.
  2. No downstream restrictions. You may not offer or impose any additional or different terms or conditions on, or apply any Effective Technological Measures to, the Licensed Material if doing so restricts exercise of the Licensed Rights by any recipient of the Licensed Material.”

 

The new trend in academic publishing is:

• offer a CC licence for Gold OA (i.e. after the publisher has money in the pocket from the author)
• or  offer a non-CC licence for Green OA, which does not give the protection of the boldfaced text from the CC licences.

It matters very much because that is what happens in the dispute between Amazon and Hachette, namely Hachette has the copyright of books but Amazon puts downstream restrictions!

Conclusion: never forget about Doctorow’s first law and always ask for a CC licence from any publisher!

Doctorow’s first law:

“Any time someone puts a lock on something that belongs to you, and won’t give you the key, you can be sure that the lock isn’t there for your benefit.”

This is from the very clear explanation about the Amazon and Hachette dispute by Cory Doctorow in Locus.

______________________________________________________________

Evidence now.

I made this post on G+, asking for info. I collect here the stuff:

• In the Open letter to the AAAS about Science Advances, (new OA journal): “The default choice of a non-commercial licence (CC BY-NC) places unnecessary restrictions on reuse and does not meet the standards set out by the Budapest Open Access Initiative. Many large funders, including Research Councils UK and the Wellcome Trust, do not recognise this as an open license. The adoption of CC BY-NC as the default license means that many researchers will be unable to submit to Science Advances if they are to conform to their funder mandates unless they pay for the upgrade to CC BY. “
• The Royal Society launches a new journal “Royal Society Open Science”. On the site of the new journal, in the section about licence to publish: they offer a licence different than CC, where they write: “4. If You decide to make the Definitive Published Version of the Article open access, this will be under a Creative Commons BY licence* [i.e. CC-BY-4.0],  You shall pay to Us the relevant fee and We shall make the Article so available from the later of the date of receipt of the relevant fee or the date of first publication of the Article.” They put  downstream restrictions for those who don’t pay them in part 6.
• the STM new model licences, read by yourself (thanks Richard Poynder for mentioning these).

Other things:

• the new journals of Cambridge University Press Forum of Mathematics Pi and Sigma offer only Gold OA with CC-BY-3.0, so there is no term of comparison with Green OA. (Have found this by downloading an article, nothing clear which is easy to find on their pages)
• the new AMS journals are Gold OA, the subscription journals are Green OA.
• the (greatest of all sites for a math or physics researcher) arXiv offers the choice between a CC-BY licence or a generic one. This is fair, because the choice is completely free left to the author.

 

UPDATE 16.09.2014: See the post AAAS vies for the title the  “Darth Vadar of publishing” by  longpd. “They  claim to support open access.  They redefine it to be a pay for publishing charge (APC)  of $3,000 USD and that restricts the subsequent use of the information in the article preventing commercial reuses such as publication on some educational blogs, incorporation into educational material, as well the use of this information by small to medium enterprises. If you really meant open access, the way the rest of world defines it, you’ll have to pay a surcharge of an additional $1,000.  But it gets worse.”

_____________________________________________________________

 

I’m doing a GUI for chemlambda

I started to work on this, here is what I am doing right now and then what I need further.

Principle. I am using the g-patterns formalism to separate the reduction of molecules from the visual representation of them.  For those who want to know more about here is the definition of g-patterns and here is the definition of moves in terms of g-patterns.

Reduction strategy. For the moment I am using a sequential strategy of reduction, with priority choices, like this:

At each reduction step do the following:

• if no LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR are present in the g-pattern, then stop, else
• identify the LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
• apply the moves from LEFT to RIGHT
• apply the COMB moves until no Arrow element
  can be eliminated
• repeat.

There is a subtlety concerning the use of CO-COMM and CO-ASSOC moves, related to the fact that I don’t want to use them directly, and related to the goal which I have, which may be one of those:

• use chemlambda regardless of its relation to lambda calculus (big goal). In this case there is no separation of reduction into self-multiplication and pure reduction. This strategy gets out quick, but in interesting ways, from lambda calculus, even if we start from a molecule which represents a lambda term.
• use chemlambda for illustrating lambda calculus (small goal). In this case the reduction strategy involves a move called SHUFFLE (which is equivalent with  CO-COMM and CO-ASSOC) and a separation of the self-multiplication from pure reduction.

Where I am now. I wrote some shell scripts, using awk and perl, to do the first strategy and I know what to do to have the second strategy as well.

Mind that I learn as I do, so probably the main shell script should be named frankenstein.sh.

What I need next.  The format of g-patterns can be easily turned into a format (I lean towards json) which can be then visualized as a force directed d3 graph. I need help here, I know there are lots of things already done, the main idea is that it should be something which doesn’t use  java, has to be free, eventually has to need only the program I prepare (which will be freely available) and a browser.

What I need after.   Several things:

• to be able to build a molecule in the window I see the graphs and to be able to convert back, to a g-pattern format. Basically this means that I need a way to add nodes which have ports, colors (red or green), such that if the node is 3valent then the cyclical order of ports is fixed. Once  added, there should be a json (say) file where the graph is saved, and then I can make a script to transform it into a g-pattern format.
• a lambda calculus parser, which takes a lambda term (input from the user) and produces the g-pattern. See this post for the description of an algorithm which does this, starting from a lambda term  with the property that if x is a bound variable then it appears under the scope of only one abstraction and moreover it does not appear as a free variable. I can write a script which does that, but I could use something which transforms a lambda term into one which can be used in the algorithm. By extension, why not a lisp to lambda calculus convertor, which can the be plugged into the pipe of the GUI?

That’s it for the moment, I APPRECIATE  USEFUL HELP, thank you.

______________________________________________________________

 

 

When priority does not matter

Perhaps the post When priority matters gives a false impression. I want to dispel that right away.

In that post we see two possible reductions, depending on the PRIORITY CHOICE, either BETA>DIST or DIST>BETA.

In the case BETA>DIST the reduction stops quickly.

On the contrary, in the case DIST>BETA  the reduction does not stop, because it enters in a cyclic process which produces an unbounded number of bubbles (i.e. loops graphical elements).

Moreover, we start from the g-pattern form of the combinator (Lx.xx)(Lx.xx).

Or, this may lead to the false impression that somehow this has anything to do with the choice between normal order reduction and  applicative order reduction from lambda calculus.

Yes, because a standard example of the difference between these reduction strategies is the following one.

Let’s denote by Omega  the combinator (Lx.xx)(Lx.xx).  Consider then the term

(Lx.z) Omega

Under the normal order reduction this term suffers one beta reduction

(Lx.z) Omega –BETA–> z

and that’s all, the reduction stops.

 

On the contrary, under the applicative order reduction strategy, the reduction never stops, because we first try to reduce Omega, leading to a cycle

(Lx.z) Omega –BETA–> (Lx.z) Omega

 

The question is: is there any connection between these two phenomena?

• is the sequential chemlambda reduction with BETA>DIST like normal order reduction in lambda calculus?
• is the sequential chemlambda reduction with DIST>BETA like applicative order reduction?

No, not the slightest.

In order to prove this I shall reduce in chemlambda with the sequential strategy the g-pattern which represents the term  (Lx.z) Omega. Let’s see what happens, but first let me remind what we do.

See the 1st part and 2nd part of the description of the conversion of lambda terms into g-patterns.

The  sequential strategy is described by the following algorithm. I write it again because the g-pattern of Lx.z brings a termination node “T”, therefore we have to consider also the local pruning moves LOC-PR.

See the post about definition of moves with g-patterns.

The algorithm of the sequential reduction strategy is this. At each reduction step do the following:

• if no LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR are present in the g-pattern, then stop, else
• identify the LEFT patterns of the moves BETA, DIST, FAN-IN and LOC-PR. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
• apply the moves from LEFT to RIGHT
• apply the COMB moves until no Arrow element
  can be eliminated
• repeat.

The PRIORITY CHOICE means a predefined choice between doing one of the two moves in conflict. The conflict may be between BETA and DIST, between  BETA and LOC-PR or between DIST and LOC-PR.

In the following we shall talk about the PRIORITY CHOICE only if needed.

In the first picture we see, in the upper side, the g-pattern which represents the term (Lx.z) Omega, then the first reduction step.

I kept the same names for the ports from the last post and I added new names for the ports of the new graphical elements.

 

First, remark that the g-pattern which represents (Lx.z) is

L[z,n2,n1] T[n2]

I named by “z” one of the ports of the lambda node L, which would correspond to the variable z of the term Lx.z. But recall that chemlambda does not use variable names, so the name “z” is there only by my choice of names for the port variables, could be anything instead (which was not used before in one of the g-pattern’s ports).

Then, A[n1,1,0] corresponds to the application of something linked to the port n1 (namely the g-pattern of (Lx.z), i.e. L[z,n2,n1] T[n2]) to something linked to the port 1 (i.e. the g-pattern of Omega, which was discussed in the post “When priority matters”).

Nice! What happened?

• there is an Arrow element which does not disappear, Arrow[z,0]. This is something which corresponds to the g-pattern of z, seen as lambda calculus term.
• and there is another g-pattern, disconnected from that Arrow[z,0] graphical element.

So, in a sense, this looks like the result of the normal order reduction, but no priority choice was involved!

However, the chemlambda sequential reduction continues, like explained in the picture of the 2nd reduction step.

 

 

 

OK, the Arrow[z,0] still exists after the reduction step, and a LOC-PR move appear.

Let’s see what happens in the 3rd reduction step.

 

The reduction stops here. There is nothing more to do, according to the sequential reduction strategy.

Differently from the reduction of Omega alone, explained in the previous post, this time there is NO PRIORITY CHOICE NEEDED.

Ergo, the priority choice has nothing to do here. The sequential chemlambda reduction of the g-pattern corresponding to (Lx.z) Omega stops after 3 steps, no matter which was the PRIORITY CHOICE made before the start of the computation.

_________________________________________________________

 

When priority matters

I continue with the analysis of chemlambda with the very simple sequential strategy. In this post I want to show you that priority really matters, by using an old example from the Metabolism of loops.

The goal is to see how the g-pattern of the combinator

(Lx.xx) (Lx.xx)

reduces in chemlambda with the sequential strategy.

See the 1st part and 2nd part of the description of the conversion of lambda terms into g-patterns.

The simple sequential strategy is the following: at each reduction step do the following:

• if no LEFT patterns of the moves BETA, DIST, FAN-IN are present in the g-pattern, then stop, else
• identify the LEFT patterns of the moves BETA, DIST, FAN-IN. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
• apply the moves from LEFT to RIGHT
• apply the COMB moves until no Arrow element is present
  can be eliminated
• repeat.

The PRIORITY CHOICE means a predefined choice between doing one of the two moves in conflict.

In this post it will be about the priority between BETA and DIST moves.

Mind that the PRIORITY CHOICE is fixed before the start of the computation.

However, in the following I shall mention the choice when it will be needed.

OK, so let’s start with the g-pattern which represents the well known combinator (Lx.xx) (Lx.xx).  Is clear that as a lambda term it has no normal form,  because it transforms into itself by a beta reduction (so is a sort of a quine, if quines would have an interesting definition in lambda calculus).

As previously, you shall see that we depart quickly from the lambda calculus realm, and we go to some straightforward directions, nevertheless.

The first figure describes the first reduction step.

 

The g-pattern obtained after this first step is the one which appears as the starting point of the Metabolism of loops post.

The 2nd step is described in the next picture:

 

Technically we are already outside lambda calculus, because of the fanin node FI[15,12,6].  (We don’t split the computation into pure reduction and pure self-multiplication.)

Let’s see the 3rd step.

 

Look well at the g-pattern which we get after the 3rd step, you’ll see it again, maybe!

The 4th step is the one which will prepare the path to conflict.

 

In the 5th step we have conflict:

 

The 5th step finishes in a different manner, depending on the PRIORITY CHOICE (which is fixed from the beginning of the computation).

Let’s suppose that we choose DIST over BETA. Then the 5th step looks like this:

 

Wow, the g-pattern after the 5th step is the same as the g-pattern after the 3rd step, with a loop graphical element added.

This means that further the computation will look alike the 4th step, then 5th step again (with the same priority choice, which is fixed!). A new loop will be generated and the computation will never stop, producing an endless string of loops.

Bubbles!

Now, let’s see what happens if the PRIORITY CHOICE is BETA over DIST.

Then the 5th step looks like this:

 

The 5th step produced 2 loops and the shortest ouroboros, a fanout node with one out port connected to the in port, namely FO[13,1,13].

The computation then stops!

______________________________________________________

So, depending on the priority choice, we have either a computation which produces bubbles without end, or a computation which stops.

It is logical. Indeed, if the priority choice is DIST over BETA, this induces the choice of increasing the number of nodes of the g-pattern. From here, it may happen, as it is the case in this example, that a cyclic behaviour is induces.

On the other side, the priority choice BETA over DIST decreases the number of nodes, thus increasing the chances for a computation which stops eventually.

Both choices are good, it depends on what we want to do with them. If we want to compute with graphs resembling chemlambda quines, because they look like living organisms with a metabolism, then the choice DIST over BETA is a good one.

If we want to have a computation which stops (dies, would say a biologist) then BETA over DIST seems better.

_____________________________________________________

Quines in chemlambda

I propose the following definition of a quine, adapted to chemlambda.

In chemlambda with the sequential strategy, a quine is a g-pattern with the property that after one reduction step it transforms into another g-pattern which is the same as the initial one, up to renaming of the port variables.

Therefore: we start with a g-pattern “P”. Then

• we identify all the LEFT g-patterns for the moves BETA, DIST, FAN-IN (see here the definition of moves)
• in case of conflict (graphical elements appearing in two different LEFT g-patterns) we keep the g-pattern which has priority, according to a predefined priority of moves (for example DIST over BETA, or BETA over DIST,..)
• we perform all the possible moves by changing the identified LEFT g-patterns with the RIGHT g-patterns
• we repeat the COMB moves which serve to eliminate the Arrow elements until no Arrow element is present.

We obtain  a g-pattern, let’s call it P’.

If there is a renaming of the port variables of P’ such that, after renaming, P’ is identical with P, then P is a chemlambda quine.

Otherwise said, if P’ is identical with P as graphs, then P is a quine.

___________________________________________

Let’s think a bit: a DIST move adds 2 nodes, a BETA or a FAN-IN move remove 2 nodes, therefore, in order to hope to have a quine, we need to have the possibility to do at  least a DIST move. That means that a quine has to contain at least the RIGHT g-pattern of a DIST move. Implies that a quine must have at least 4 nodes.

A quick inspection shows that the two RIGHT g-patterns of the two DIST moves cannot be made into quines.

Therefore a quine must have at least 5 nodes. Among the nodes have to be L, A, FO, FI. But in order to reconstruct the L node and the A node one needs two DIST moves, which gives a lower bound of 8 nodes for a quine.

I believe that there is no quine with less than 9 nodes, such that the reductions never involve a choice of priority of moves.

__________________________________________

Here is now a bigger quine:

 

It’s a walker from the ouroboros series, walking on a circular train track with only one pair of nodes L and FO.

It has 28 nodes and 42 edges.

Can you find a smaller quine?

_________________________________________________________

UPDATE: Here is a small quine with 9 nodes and 14 edges:

 

_________________________________________________________