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:

 

pred_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:

 

small_quine

_________________________________________________________

 

 

 

 

 

Advertisements

5 thoughts on “Quines in chemlambda”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s