Yuriy explores the idea to replace conventional CA rule with algebraic operation by grouping pairs of cells (Pedersen 1992, Moore 1997). Then, the ECA evolution can be computed bu groupoid multiplications of neighboring elements.
Generally, the complexity of computation of evolution is N^2. Can one do better? Yes, under certain conditions. Namely, there are certain "shortcut" identities. One can empirically search for these identties, but can they be derived?
A "basis" is a set of identities from which all other identities follow (these are like axioms). "Finitely based" groupoids have finite basis. 4-element groupoids are not necessarity finitely based: some "true" identities cannot be derived from other lower-degree identities. There is a recursive algorithm that would determine if groupoid is finitely based (is there?)
Here, Yuriy is making a hint on a connection between incompressibility and non-finitely-based groupoids. In particular, the fact that 6 is the least order of semigroup without a finite basis for identities vs. NKS book, page 887. Traditional math is based on a finite number of axioms, and to develop complexity, one needs(?) non-finitely-based systems. The less identities are there, the more interesting is
the structure.
Pretty cool, I would say. It would be interesting to see how those identities appear in the numerously drawn CA evolution pictures. Something like longer-term rules?
Comments