There is now a page to check if a graph is a quine. This is done by a clarification of the notion of a quine graph.

The initial definition for a quine graph is: one which has a periodic evolution under the greedy algorithm of rewrites. The greedy algorithm performs at each step the maximal number of non-conflicting rewrites.

Mind that for some graphs, at one moment there might be more than one maximal collections of non-conflicting rewrites. Therefore the greedy algorithm is not deterministic, but almost.

In the js simulations there is performed one graph rewrite at each step, so how can we modify this to be able rto check if a graph is a quine?

The answer is to introduce an age of the nodes and links of the graph. There is an age (global) counter which counts the number of steps. Each new node and each new edge receive an “age” field which keeps the age of the birth of the said node or link.

The age of a rewrite pattern is then the maximum of ages of it’s nodes and links.

The “random choices” lets the initial reduction algorithm as is. That means the rewrites are executed randomly, with the exception of “COMB” rewrites which are always executed first.

The “older is first” executes always the rewrites on the oldest rewrite patterns (with the exception of “COMB” rewrites which are executed first, when available. The effect is that the algorithm reduces sequentially maximal collections of non-conflicting graph rewrites!

Therefore the definition of a quine graph should be modified to: a graph which has bounded (number of nodes and links) evolution under the “older is first” algorithm.

It is however intriguing the stabilising effect of “older is first”. Just look at the 9_quine, with the “older is first” it never dies, as expected, but under “random choices” it does.

Similarly, use the new page to look at the behaviour of the 10_nodes quine. It either dies immediately or it never dies. This is understandable from the definition, because this quine has either a maximal collection of rewrites which kills it or another maximal collection of rewrites which transforms it into a graph which ahs periodic evolution from that point.

But what is intriguing is the suggestion that there should be a tunable parameter, between “random choices” and “older is first”, namely a parameter in the probablility of the rewrites which decrease with age (i.e. older patterns are more probable to be rewritten than the newer ones). At one extreme older patterns are always executed first. At the other extreme there is the same probability no matter the age of the pattern.

To have probabilities strongly depending on the age of the pattern stabilize the evolution of a quine graph: it may die quick or it lives forever. Probably it does not reproduce.

On the other side, a lower dependence on age implies a more natural evolution: the quine may now die or reproduce.

### Like this:

Like Loading...