A quine in Lafont’ Interaction combinators

I continue with a second post about Y. Lafont Interaction combinators. Here is the first one.

In the Figure 3 from the article is given an example of a nonterminating computation:


This is a quine. Indeed it is a graph which has a periodic evolution under the deterministic greedy reduction algorithm, using the interaction rules (i.e. the graph rewrites) of interaction combinators.

By comparison, a chemlambda quine is a molecule (graph in chemlambda) which has a periodic evolution under the deterministic greedy reduction algorithm which uses the chemlambda graph rewrites, with the priority of the rewrites set to “viral”, i.e. the DIST family of rewrites comes first. In chemlamdba is needed a prority of rewrites (for the deterministic algorithm) because there exist conflicts between the rewrites, i.e. overlaping left patterns.

About a third of the molecules from the library are chemlambda quines and they are interesting mostly when reduced with the random reduction algorithm. While for interaction combinators the random reduction algorithm brings nothing new (the system is confluent), for chemlambda with the random reduction algorithm the system is not confluent and the chemlambda quines may die. All of the quines from the library are at best immortal, i.e. the probability of death does not depend on the age of the molecule.

A reason for this phenomenon is that all these chemlambda quines don’t use termination nodes (which correspond to the epsilon nodes of interaction combinators). The smallest chemlambda quine without T nodes is the 9_quine, which has  9 nodes. But we may use termination nodes and produce a quine which is similar to Lafont’ example:


In mol notation this quine is:

FO 1 2 3
T 2
FOE 3 4 1
T 4

The animation is obtained with the scripts from the chemlambda repository, in the same way as those used for the comparison with the Dynamic GOI Machine. In order to obtain a deterministic reduction all weights (i.e. all parameters “wei_*” from the relevant awk script were set to 0.

You see that this is really a 6 nodes quine, why? Because even in Lafont example, a deterministic greedy reduction would lead at step 2 to the simultaneous application of rewrites which increase the number of nodes and of those which decrease the number of nodes, so a correct application of the deterministic greedy algorithm would be similar with the example from chemlambda.

Maybe it would be interesting (as a tool) and straightforward to modify the chemlambda scripts into an interaction combinators version.




2 thoughts on “A quine in Lafont’ Interaction combinators”

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s