1D CA using semisymmetric quasigroups as the transition
Posted: January 7th, 2019, 3:18 am
This came up as I was playing with tilings over the holidays, but I found some published work on the same topic in terms of cellular automata using a binary operator so I'll explain in those terms.
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.:
From these triples, applying the identities above, we construct this table:
Note that a randomly selected set of triples would most likely result in missing entries and duplicates. Also note that the table, if it does work, will always be a Latin square.
Enumerating up to n=6 and putting triple sets in canonical form (since many are equivalent up to renumbering), I found the following:
I believe the above corresponds to Sloane sequence A076018, ("Number of systems with n elements having with one binary operation satisfying the equation B(AB)=A (semisymmetric quasigroups). Isomorphic systems and systems differing by a transposition have been omitted.") (Both of these sequences come from Richard Schroeppel; I wonder what his interest is.)
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.
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.
- Screen Shot 2019-01-06 at 10.14.53 PM.png (18.89 KiB) Viewed 2691 times
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.
- Screen Shot 2019-01-06 at 10.47.10 PM.png (196.45 KiB) Viewed 2691 times
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.
- Screen Shot 2019-01-06 at 9.03.02 PM.png (710.08 KiB) Viewed 2691 times
I didn't previously say anything on account of not having anything worthwhile to add, but since noone else has replied I'd like to make it known that a lack of replies does not indicate a lack of interest, at all.