Hard Combinators

Analyzing possible modifications of interaction combinators' representation suitable for uniform memory led to the subject of so-called hard combinators. In particular, trying to compose a universal equivalent of {γ, δ} such as {φ, ψ, ξ} resulted in necessary rotation of ξ with respect to its principal port in some cases. The hard combinators discovered were introduced in a quite recent same-name paper by Bechet and Lippi, namely in 2008. Some idea of Bechet most probably related to the subject was actually mentioned in the paper by Lafont, although without any details and only referencing private communication instead.

Somewhat similar to hard combinators could be of use for uniform memory implementation of interaction systems from the view point of memory-preserving property. Specifically, the total amount of cells involved in a rule for a cut should remain the same before and after reduction. This way, implementation of duplication and annihilation as well as free cells buffer appear to be explicitly embedded into a formal interaction system.

There are also some slides demonstrating the hard combinators. They are available through the following address:

http://iml.univ-mrs.fr/ldp/Seminaire/documents0607/lippi.pdf

Using Lafont's notation, the resulted system can be described as a system of interaction nets with agents of types in {0, 1, –, +}, which has been proved to be Turing-complete with the following interaction rules:

0[0(x, y), x] >< –[–(y)], 1[1(x, y), x] >< –[+(y)];
0[x, 0(y, x)] >< +[–(y)], 1[x, 1(y, x)] >< +[+(y)].