ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

1D CA using semisymmetric quasigroups as the transition

For discussion of other cellular automata.

1D CA using semisymmetric quasigroups as the transition

Postby pcallahan » 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.
Screen Shot 2019-01-06 at 10.14.53 PM.png
Screen Shot 2019-01-06 at 10.14.53 PM.png (18.89 KiB) Viewed 613 times


...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.:
[(0, 0, 0), (0, 1, 2), (0, 2, 3), (1, 1, 1), (2, 2, 2), (3, 1, 0), (3, 2, 1), (3, 3, 3)]


From these triples, applying the identities above, we construct this table:
0 2 3 1
3 1 0 2
1 3 2 0
2 0 1 3

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:
((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))

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.
Screen Shot 2019-01-06 at 10.47.10 PM.png
Screen Shot 2019-01-06 at 10.47.10 PM.png (196.45 KiB) Viewed 613 times


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.
Screen Shot 2019-01-06 at 9.03.02 PM.png
Screen Shot 2019-01-06 at 9.03.02 PM.png (710.08 KiB) Viewed 613 times
pcallahan
 
Posts: 132
Joined: April 26th, 2013, 1:04 pm

Re: 1D CA using semisymmetric quasigroups as the transition

Postby pcallahan » January 8th, 2019, 1:35 pm

BTW, if anyone is interested in any of this, I can post code some time. I haven't really had a chance to clean up the mess of tinkering. I have been making heavy use of Python with turtle graphics, which is surprisingly up to the task (probably just because computers are so much faster than they used to be). You can even run turtle in repl.it Python. (It also helps that I am generating static pictures too).

I also do most enumerations in Python. (I did most of the life searches in ANSI C way back when and I shudder to think how fast that would run today; I don't have time for the hassle right now, maybe post-retirement).
pcallahan
 
Posts: 132
Joined: April 26th, 2013, 1:04 pm

Re: 1D CA using semisymmetric quasigroups as the transition

Postby Apple Bottom » January 8th, 2019, 5:05 pm

pcallahan wrote:BTW, if anyone is interested in any of this, I can post code some time.


For the record, I'm definitely interested; I find your ideas intriguing and wish to subscribe to your newsletter, as it were. ;) 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.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!
User avatar
Apple Bottom
 
Posts: 1017
Joined: July 27th, 2015, 2:06 pm

Re: 1D CA using semisymmetric quasigroups as the transition

Postby pcallahan » January 10th, 2019, 1:56 am

Apple Bottom wrote:For the record, I'm definitely interested


OK, then. Here is some Python code that can apply the rules row by row, and it includes four examples of rules. It displays them with turtle graphics, achieving speeds reminiscent of watching text arriving from a 300 baud modem (for those who remember the 80s and/or fans of the movie WarGames). It is faster if you remove the update after each cell is rendered, but it seems to work more reliably with continuous update on repl.it where you can run it through this link.

This includes three examples of symmetric rules (quasigroups) mentioned in the previous posting. It just starts with the "tile" set or list of triples, and converts each into function f such that for triple (a, b, c): c = f(a, b), a = f(b, c), b = f(c, a).

The rule110 embedding is included as well. This does not convert into a function as above, because for some x, y, f(x, y) has up to three possible values and in some cases does not have a value (fixable by adding more tiles, but the result is still non-deterministic). It is a true embedding though, in the sense that if a horizontal row is filled in with only 0s and 1s, then the orientation of subsequent rows is fixed and applying the symmetric constraints (forced by data) results in rule 110 for every other row.

This is the same code I placed at repl.it for running locally.

import turtle
import sys

# run xor|cyclic3|triangles4|rules110 with preset parameters
name = 'triangles4'
if len(sys.argv) > 1:
  name = sys.argv[1]

RULE_TILES = {
    'xor': ((0, 0, 0), (0, 1, 1)),
    'cyclic3': ((0, 0, 1), (0, 2, 2), (1, 1, 2)),
    'triangles4': ((0, 0, 0), (0, 1, 2), (0, 2, 3),
                   (1, 1, 1), (2, 2, 2), (3, 1, 0),
                   (3, 2, 1), (3, 3, 3)),
    'rule110': ((0, 0, 2), (0, 1, 3), (1, 0, 2), (1, 1, 4),
                (2, 2, 0), (2, 3, 1), (3, 2, 1), (3, 4, 1),
                (4, 2, 1), (4, 4, 0))
}

COLORS = ['white', 'black', '#68ff68', '#6868ff', '#ff2222', 'purple', '__skip__']

SIDE_LEN = 7

PRESETS = {
  'xor': {
    'init': '00000000000000000100000000000000000',
    'steps': 32,
    'side_len': SIDE_LEN
  },
  'cyclic3': {
    'init': '000000000000000001201200000000000000000',
    'steps': 50,
    'side_len': SIDE_LEN
  },
  'triangles4': {
    'init': '0000000000000111111111112222222',
    'steps': 44,
    'side_len': SIDE_LEN
  },
  'rule110': {
    'init': '00000000000000000000000000000000000000000001',
    'steps': 50,
    'side_len': SIDE_LEN
  }
}


def make_function(tiles):
    table = {}
    for tile in tiles:
        for i in range(-2, 1):
            table.setdefault(tile[i], {}).setdefault(tile[i + 1], set()).add(tile[i + 2])
    for k1 in table:
        for k2 in table[k1]:
            table[k1][k2] = sorted(list(table[k1][k2]))
    return table


def hex(state, side_len=SIDE_LEN):
    color = COLORS[state]
    if color == '__skip__':
        return

    turtle.pendown()
    turtle.fillcolor(color)
    turtle.begin_fill()
    for i in range(6):
        turtle.right(30)
        turtle.forward(side_len)
        turtle.right(30)
    turtle.end_fill()
    turtle.penup()



def follow_edges(turn1, turn2, side_len=SIDE_LEN):
    turtle.penup()
    turtle.right(turn1)
    turtle.forward(side_len)
    turtle.right(turn2)
    turtle.forward(side_len)
    turtle.right(-turn1 - turn2)
     

def next_on_row(side_len=SIDE_LEN):
    follow_edges(30, -60, side_len)


def down_right(side_len=SIDE_LEN):
    follow_edges(30, 60, side_len)


def down_left(side_len=SIDE_LEN):
    follow_edges(150, -60, side_len)


def hex_row(row, side_len=SIDE_LEN):
    turtle.penup()
    pos = turtle.position()
    for state in row:
        hex(state, side_len)
        turtle.update()   
        next_on_row(side_len)
    turtle.setposition(pos)


def apply_rule(row, table):
    return [table[row[i]][row[(i + 1) % len(row)]][0] for i in range(len(row))]


def display(row, table, steps, side_len=SIDE_LEN):
    shift = 0
    for i in range(steps):
        hex_row(row[-shift:] + row[:-shift], side_len)
        turtle.update()
        row = apply_rule(row, table)
        # shift the row so it zigzags instead of drifting right
        if i % 2:
            shift = (shift + 1) % len(row)
            down_left(side_len)
        else:
            down_right(side_len)


init = [int(c, 16) for c in PRESETS[name]['init']]
steps = PRESETS[name]['steps']
side_len = PRESETS[name]['side_len']
table = make_function(RULE_TILES[name])

turtle.tracer(0, 0)
turtle.hideturtle()
turtle.penup()
turtle.setposition(-300, 300)
turtle.pencolor('gray')
display(init, table, steps, side_len)
turtle.update()



Here is a low-res combined screenshot of the four CAs/tilings, scaled down in the hope that conwaylife will display it without scrolling.
Screen Shot 2019-01-09 at 9.23.55 PM.png
Screen Shot 2019-01-09 at 9.23.55 PM.png (170.98 KiB) Viewed 487 times
pcallahan
 
Posts: 132
Joined: April 26th, 2013, 1:04 pm

Re: 1D CA using semisymmetric quasigroups as the transition

Postby pcallahan » January 10th, 2019, 11:17 am

For completeness, here is the Python code for enumerating rotationally symmetric rules (or, equivalently, semisymmetric quasigroups). I wrote this before knowing what I was enumerating, so it should be a lot faster to enumerate semisymmetric quasigroups as "Latin squares with each row and column a permutation and corresponding rows and columns are inverse permutations" (Richard Schroeppel in https://oeis.org/A076016) and then collecting the triangles from the quasigroup table.

import sys


def triples(n):
    for i in range(n):
        for j in range(i, n):
            for k in range(j, n):
                yield i, j, k
                if i < j and j < k:
                    yield k, j, i


def getpairs(triple):
    for i in range(-2, 1):
        yield triple[i], triple[(i + 1) % 3]


def cover(pairset, triples, depth, used, target):
    # yield subset and return if every pair is covered by a triangle
    if len(pairset) == target:
        yield tuple(used)
        return

    # return if there are no more triples to try
    if depth == len(triples):
        return

    # recurse without adding the triple
    for res in cover(pairset, triples, depth + 1, used, target):
        yield res

    # if triple does not reuse any covered pairs, recurse with it added
    triple = triples[depth]
    pairs = list(getpairs(triple))
    if pairset.isdisjoint(pairs):
        pairset.update(pairs)
        used.append(triple)
        for res in cover(pairset, triples, depth + 1, used, target):
            yield res
        used.pop()
        pairset.difference_update(pairs)


def permutations(n, choices, depth):
    if depth == n:
        yield tuple(choices)

    for i in range(depth, n):
        choices[i], choices[depth] = choices[depth], choices[i]
        for res in permutations(n, choices, depth + 1):
            yield res
        choices[i], choices[depth] = choices[depth], choices[i]


def map_canonical(triples):
    map = {}
    for triple in triples:
        rotation = triple
        for i in range(len(triple)):
            map[rotation] = triple
            rotation = rotation[-1:] + rotation[0:-1]
    return map


def normalize_triples(triples, canonical):
    vals = [canonical[triple] for triple in triples]
    vals.sort()
    return tuple(vals)


def recolor(triples, permutation, canonical):
    return normalize_triples([(tuple(permutation[x] for x in triple))
                               for triple in triples], canonical)


def is_canonical(triples, n, canonical):
    triples = normalize_triples(triples, canonical)
    for permutation in permutations(n, list(range(n)), 0):
        if triples > recolor(triples, permutation, canonical):
            return False
    return True


n = int(sys.argv[1])
all_triples = list(triples(n))
canonical = map_canonical(all_triples)


for v in cover(set(), all_triples, 0, [], n * n):
    if is_canonical(v, n, canonical):
        print(tuple(sorted(v)))


E.g. if you put it in the file rulecoverings.py, this will give the 5-state rules in canonical form:
python ~/scratch/rulecoverings.py 5
((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))


I have run this as far as 6, which took under 25 minutes on my laptop. 7 is probably doable and based on https://oeis.org/A076018 should return 34 results.
pcallahan
 
Posts: 132
Joined: April 26th, 2013, 1:04 pm


Return to Other Cellular Automata

Who is online

Users browsing this forum: 2718281828 and 3 guests