We start with a binary operator ○ and a (small) finite set to operate on. Given three values a, b, c let
a ○ b = c.
By definition, ○ is a semisymmetric quasigroup if it satisfies b ○ (a ○ b) = a. This is a little more terse than I need for my purposes, so note that as a consequence:
b ○ c = a (because a ○ b = c) and likewise, because c ○ (b ○ c) = b, it follows that c ○ a = b.
Another way to look at this is as the following hexagonal tile. In this case, given two of the rhombus colors, the third is uniquely determined by applying ○ to the values in clockwise order. A semisymmetric quasigroup is thus equivalent to a set of tiles for a given set of colors such that every pair of colors in clockwise or counterclockwise order is represented in exactly one tile. ...Or I believe so, assuming I'm not missing some subtlety. I actually came about this in reverse. I wrote a program to enumerate the tile sets of interest using a brute force backtracking approach in a python script, counting the number of distinct sets for each n=1, 2, 3 ... and got 1, 2, 3, 18, 120, 2880.
I looked it up in Sloane and found that it had a name and some other nice properties. After working out the implications of the definition, I was convinced it was not coincidental (thanks Sloane!).
Let the members of some quasigroup be 0, 1, ..., n-1. Then a set of tiles can be given as a list of triples, e.g.:
Code: Select all
[(0, 0, 0), (0, 1, 2), (0, 2, 3), (1, 1, 1), (2, 2, 2), (3, 1, 0), (3, 2, 1), (3, 3, 3)]
Code: Select all
0 2 3 1
3 1 0 2
1 3 2 0
2 0 1 3
Enumerating up to n=6 and putting triple sets in canonical form (since many are equivalent up to renumbering), I found the following:
Code: Select all
((0, 0, 0), (0, 1, 1))
((0, 0, 1), (0, 2, 2), (1, 1, 2))
((0, 0, 0), (0, 1, 2), (1, 1, 1), (2, 1, 0), (2, 2, 2))
((0, 0, 0), (0, 1, 2), (0, 2, 3), (1, 1, 1), (2, 2, 2), (3, 1, 0), (3, 2, 1), (3, 3, 3))
((0, 0, 0), (0, 1, 1), (0, 2, 3), (1, 2, 2), (1, 3, 3), (3, 2, 0))
((0, 0, 0), (0, 1, 1), (0, 2, 2), (0, 3, 3), (1, 2, 3), (3, 2, 1))
((0, 0, 0), (0, 1, 2), (0, 3, 4), (1, 1, 3), (1, 4, 4), (2, 1, 0), (2, 2, 4), (2, 3, 3), (4, 3, 0))
((0, 0, 0), (0, 1, 1), (0, 2, 3), (0, 3, 4), (1, 2, 4), (2, 2, 2), (3, 2, 1), (3, 3, 3), (4, 2, 0), (4, 3, 1), (4, 4, 4))
((0, 0, 0), (0, 1, 1), (0, 2, 3), (0, 3, 4), (1, 2, 2), (1, 3, 3), (1, 4, 4), (4, 2, 0), (4, 3, 2))
((0, 0, 0), (0, 1, 1), (0, 2, 2), (0, 3, 3), (0, 4, 4), (1, 2, 3), (1, 3, 4), (4, 2, 1), (4, 3, 2))
((0, 0, 1), (0, 2, 2), (0, 3, 3), (0, 4, 5), (1, 1, 2), (1, 3, 4), (1, 5, 5), (2, 3, 5), (2, 4, 4), (4, 3, 1), (5, 3, 2), (5, 4, 0))
((0, 0, 1), (0, 2, 2), (0, 3, 3), (0, 4, 4), (0, 5, 5), (1, 1, 2), (1, 3, 4), (1, 4, 5), (2, 3, 5), (4, 3, 2), (5, 3, 1), (5, 4, 2))
((0, 0, 0), (0, 1, 1), (0, 2, 3), (0, 3, 4), (0, 4, 5), (1, 2, 5), (2, 2, 2), (2, 4, 4), (3, 2, 1), (3, 3, 3), (3, 5, 5), (4, 3, 1), (5, 2, 0), (5, 4, 1))
((0, 0, 0), (0, 1, 1), (0, 2, 3), (0, 3, 4), (0, 4, 5), (1, 2, 2), (1, 3, 5), (1, 4, 4), (3, 3, 3), (4, 3, 2), (5, 2, 0), (5, 3, 1), (5, 4, 2), (5, 5, 5))
((0, 0, 0), (0, 1, 1), (0, 2, 3), (0, 3, 4), (0, 4, 5), (1, 2, 2), (1, 3, 5), (2, 4, 4), (3, 3, 3), (4, 3, 1), (5, 2, 0), (5, 3, 2), (5, 4, 1), (5, 5, 5))
((0, 0, 0), (0, 1, 1), (0, 2, 3), (0, 4, 5), (1, 2, 4), (1, 3, 5), (2, 2, 2), (2, 5, 5), (3, 2, 0), (3, 3, 4), (4, 2, 1), (4, 4, 4), (5, 3, 1), (5, 4, 0))
((0, 0, 0), (0, 1, 1), (0, 2, 3), (0, 4, 5), (1, 2, 4), (1, 3, 5), (2, 2, 2), (2, 5, 5), (3, 2, 0), (3, 3, 3), (3, 4, 4), (4, 2, 1), (5, 3, 1), (5, 4, 0))
((0, 0, 0), (0, 1, 1), (0, 2, 2), (0, 3, 4), (0, 4, 5), (1, 2, 3), (1, 3, 5), (1, 4, 4), (3, 3, 3), (4, 3, 2), (5, 2, 1), (5, 3, 0), (5, 4, 2), (5, 5, 5))
((0, 0, 0), (0, 1, 1), (0, 2, 2), (0, 3, 3), (0, 4, 5), (1, 2, 4), (1, 3, 5), (2, 3, 4), (4, 3, 1), (4, 4, 4), (5, 2, 1), (5, 3, 2), (5, 4, 0), (5, 5, 5))
To use these in a 1D CA, construct the corresponding tables and simply apply ○ to two adjacent values in a row to produce the values in the next row. This displays symmetrically if rows are given as hexagons with corners pointing up. Note that you don't have to apply the CA row by row. Because the rule is symmetric, you can complete any neighborhood of hexagons for which either the top two values are known, or the bottom value and one of the top two. Here is an example using ((0, 0, 1), (0, 2, 2), (1, 1, 2)) (0=white, 1=black, 2=red) and completing a hexagon by spiraling out from the center. Alternatively, the rule can be implemented conceptually by tiling the plane with the tiles shown so that the colors match up including the boundary between the rhombuses. The tiles may be rotated but may not be reflected.
Finally, here is a sampling of some of the other rules with their tiles shown graphically. For the most part, they have a Sierpinski triangle/XOR flavor to them but might be more interesting with different initial conditions.
I am not sure if it is even reasonable to hope to find a universal (Turing complete) tile set that has to be a quasigroup like this. Any thoughts? As noted in a previous post, I can embed rule 110 in a tile set with rotations, but that tile set does not determine a quasigroup, since some tilings lead to multiple or no possible completions.