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: