On a set with an operation which has a neutral element, there is an algebraic axiom which is equivalent with both associativity and commutativity of the operation. I call it the shuffle (does it have a name?).

It is this one:

**(ab)(cd) = (ac)(bd)**

so the middle terms b and c switch their position.

Of course, by duality, that means that there is an axiom which is equivalent with both co-associativity and co-commutativity, in an algebra with co-unit.

This is a justification for the existence of TWO fanout nodes in chemlambda, called FO and FOE. The graphical representation of the shuffle, called now the shuffle trick, is simply a combination of two graph rewrites, as shown in the demo on the shuffle trick.

On this blog the shuffle trick is mentioned several times, and the “shuffle move” is proposed as various compositions of moves from graphic lambda calculus.

But the CO-COMM and CO-ASSOC moves from graphic lambda calculus are no longer needed, being replaced by FO-FOE and FI-FOE (aka fan-in) moves. This is good because the graph rewrites which express the associativity and commutativity are too symmetric, they don’t have a natural direction of application, therefore any choice of a preferred direction would be artificial.

The shuffle trick is essential for self-multiplication, where there has to be a way to multiply trees made by FO nodes, in such a way so that the leaves of the copies of the tree are not entangled, see this demo.

________________________________________________

Advertisements

Nice! Next I want to see examples of tricks to limit associativity and commutativity to create a channel which replicates across a distance. 🙂

The post explains that associativity and commutativity are eliminated.