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:

_________________________________________________________

### Like this:

Like Loading...

*Related*

Are quines equivalent to Mask-Core graphs?

https://chorasimilarity.wordpress.com/2013/10/19/a-machine-for-computing-the-ackermann-function-in-graphic-lambda-calculus/

No, the mask-core construction is just an I/O interface.