Penrose tilings, hyperbolic tesselations

[gexahedron]

Hi! I have 2 questions:
1. There exist such non-periodic tiling of a plane as a Penrose tiling (http://en.wikipedia.org/wiki/Penrose_tiling), there is even a Java-applet that can simulate life-like behaviour within it (http://www-users.york.ac.uk/~ndlo100/lazyapplet.shtml). And there are infinitely many different Penrose tilings, but they share an interesting property, that it is self-similar, so the same finite patterns occur at larger and larger scales in all Penrose tilings. An author of this applet found some oscillators and still lifes (some examples you could find here: http://www-users.cs.york.ac.uk/~susan/b ... uto08b.pdf). But could there exist some kind of spaceships (because it should be very difficult to fly over a non-periodic grid)?
2. Have anybody tried simulating life on any hyperbolic tesselations?

[apg]

There have been cellular automata on regular tilings of the hyperbolic plane, including one which solves 3-SAT (the archetypal NP-complete problem) in polynomial time. Of course, this is not a proof that P = NP, as it utilises the exponential parallelisation of hyperbolic computing.

Indeed, this also demonstrates why it is difficult to simulate a pattern on the hyperbolic plane, and should take exponential time to run it.

[Tropylium]

2. Have anybody tried simulating life on any hyperbolic tesselations?

Took a shot at this today. I dabbled a bit around on the pentagonal tiling, which seems like the simplest analog for a square grid. Indeed, many patterns can be transferred over just fine; from Life, a block, an aircraft carrier, or a beacon work intact, and you can construct a 5-cell "tub", an 8-cell "beehive", a 10-cell "loaf", a 12-cell "pond" etc. as well.

It quickly turns out this will not be very fruitful, however. Any finite pattern (or an infinite one, for that matter) can be encased in a box where all edges are 1 or 2 cells: take the bounding box and expand by one layer of pentagons (squinges?) wherever it's not ≤2 cells wide already. No A012B3 pattern is going to escape those bounds… hence, no spaceships, no growing methuselahs, no anything of the sort.

If we DO allow B2, then the domino engine issue rears its head again. Not only will one shoot out to infinity just like in Flatland, but hyperbolic space is also too wide for any wings to keep up with a lightspeed engine. So we always get at least a replicator stream.

I've also been looking at elliptic grids. The tetrahedron is just about trivial, and cube/octahedron/dodecahedron are quite quickly solved as well (where by "solved" I mean "determined the evolution of every pattern under every rule"); patterns either oscillate within their own symmetry group (eg. in B0/S4 or B14/S0, a cube with one face living makes a p4 oscillator) or reduce to a higher symmetry group. The icosahedron might support some interesting larger periods, haven't really investigated yet.

Seems though that grids non-Euchlidian only at some locations might have more stuff to investigate. Also another thing that suggests itself as well at this poing is going all General Relativity by allowing cells to carve dimples for themselves…

[Scorbie]

Apologies for bringing up a very very old topic. I was interested in Penrose Tiling CA, heard that you could do that in Ready but couldn't figure out how to make your own rules, and saw this link a while ago (Thanks A for Awesome!) and tweaked it a bit (actually, did almost nothing) to make it work and support totalistic rules. Here it is. It is basically a primitive version of soup searcher.
Note: This depends on cairo(installed in linux and probably mac too) and pygame.

Code: Select all

#!/usr/bin/python -O

# Code from http://codegolf.stackexchange.com/questions/35827
# tiling generation code originally from http://preshing.com/files/penrose.py

import sys
import math
import time
import cairo
import cmath
import random
import pygame

#TODO: command line parameters
#------ Configuration --------
IMAGE_SIZE = (600,600)
OFFX = 300
OFFY = 300
RADIUS = 300
if __debug__: NUM_SUBDIVISIONS = 5
else: NUM_SUBDIVISIONS = 7
# Added by Scorbie
RULE=((3,),(2,3))
#-----------------------------

goldenRatio = (1 + math.sqrt(5)) / 2

class Triangle():
    def __init__(self, parent = None, color = 0, corners = []):
        self.parent = parent
        self.other_half = None
        # immediate neighbor 0 is on BA side, 1 is on AC side
        self.neighbors = [None, None]
        # all_neighbors includes diagonal neighbors
        self.all_neighbors = set()
        # child 0 is first on BA side, 1 is second, 2 is on AC side
        self.children = []
        self.color = color
        if __debug__: self.debug_color = (random.random(),random.random(),random.random())
        self.state = random.randint(0,1)
        self.new_state = 0
        self.corners = corners
        self.quad = None
    def __repr__(self):
        return "Triangle: state=" + str(self.state) + \
            " color=" + str(self.color) + \
            " parent=" + ("yes" if self.parent else "no") + \
            " corners=" + str(self.corners)
    # break one triangle up into 2-3 smaller triangles
    def subdivide(self):
        result = []
        A,B,C = self.corners
        if self.color == 0:
            # Subdivide red triangle
            P = A + (B - A) / goldenRatio
            result = [Triangle(self, 0, (C, P, B)), Triangle(self, 1, (P, C, A))]
        else:
            # Subdivide blue triangle
            Q = B + (A - B) / goldenRatio
            R = B + (C - B) / goldenRatio
            result = [Triangle(self, 1, (Q, R, B)), Triangle(self, 0, (R, Q, A)), Triangle(self, 1, (R, C, A))]
        self.children.extend(result)
        return result;
    # identify the left and right neighbors of a triangle
    def connect_immediate(self):
        o = None
        n = self.neighbors
        if self.parent:
            if self.color == 0: # red child
                if self.parent.color == 0: # red parent
                    if self.parent.neighbors[0]:
                        if self.parent.neighbors[0].color == 0: # red left neighbor
                            o = self.parent.neighbors[0].children[0]
                        else: # blue left neighbor
                            o = self.parent.neighbors[0].children[1]
                    n[0] = self.parent.children[1]
                    if self.parent.other_half:
                        n[1] = self.parent.other_half.children[0]
                else: # blue parent
                    if self.parent.neighbors[0]:
                        if self.parent.neighbors[0].color == 0: # red left neighbor
                            o = self.parent.neighbors[0].children[0]
                        else: # blue left neighbor
                            o = self.parent.neighbors[0].children[1]
                    n[0] = self.parent.children[0]
                    n[1] = self.parent.children[2]
            else: # blue child
                if self.parent.color == 0: # red parent
                    if self.parent.neighbors[1]:
                        if self.parent.neighbors[1].color == 0: # red right neighbor
                            o = self.parent.neighbors[1].children[1]
                        else: # blue right neighbor
                            o = self.parent.neighbors[1].children[2]
                    n[0] = self.parent.children[0]
                    if self.parent.neighbors[0]:
                        if self.parent.neighbors[0].color == 0: # red left neighbor
                            n[1] = self.parent.neighbors[0].children[1]
                        else: # blue left neighbor
                            n[1] = self.parent.neighbors[0].children[0]
                else: # blue child of blue parent
                    if self.corners[2] == self.parent.corners[1]: # first blue child
                        if self.parent.other_half:
                            o = self.parent.other_half.children[0]
                        n[0] = self.parent.children[1]
                        if self.parent.neighbors[0]:
                            if self.parent.neighbors[0].color == 0: # red left neighbor
                                n[1] = self.parent.neighbors[0].children[1]
                            else: #blue left neighbor
                                n[1] = self.parent.neighbors[0].children[0]
                    else: # second blue child
                        if self.parent.neighbors[1]:
                            if self.parent.neighbors[1].color == 0: # red right neighbor
                                o = self.parent.neighbors[1].children[1]
                            else: # blue right neighbor
                                o = self.parent.neighbors[1].children[2]
                        if self.parent.other_half:
                            n[0] = self.parent.other_half.children[2]
                        n[1] = self.parent.children[1]
        self.other_half = o
        if o:
            self.state = self.other_half.state
            if __debug__: self.debug_color = self.other_half.debug_color

#TODO: different seed triangle configurations
# Create wheel of red triangles around the origin
triangles = [[]]
for i in xrange(10):
    B = cmath.rect(RADIUS, (2*i - 1) * math.pi / 10)+OFFX+OFFY*1j
    C = cmath.rect(RADIUS, (2*i + 1) * math.pi / 10)+OFFX+OFFY*1j
    if i % 2 == 0:
        B, C = C, B  # Make sure to mirror every second triangle
    triangles[0].append(Triangle(None, 0, (OFFX+OFFY*1j, B, C)))

# identify the neighbors of the starting triangles
for i in xrange(10):
    if i%2:
        triangles[0][i].neighbors[0] = triangles[0][(i+9)%10]
        triangles[0][i].neighbors[1] = triangles[0][(i+1)%10]
    else:
        triangles[0][i].neighbors[1] = triangles[0][(i+9)%10]
        triangles[0][i].neighbors[0] = triangles[0][(i+1)%10]

# Perform subdivisions
for i in xrange(NUM_SUBDIVISIONS):
    triangles.append([])
    for t in triangles[i]:
        triangles[i+1].extend(t.subdivide())
    for t in triangles[i+1]:
        t.connect_immediate()

# from here on, we only deal with the most-subdivided triangles
tris = triangles[NUM_SUBDIVISIONS]

# make a dict of every vertex, containing a list of every triangle sharing that vertex
vertices = {}
for t in tris:
    for c in t.corners:
        if c not in vertices:
            vertices[c] = []
        vertices[c].append(t)

# every triangle sharing a vertex are neighbors of each other
for v,triset in vertices.iteritems():
    for t in triset:
        t.all_neighbors.update(triset)

# combine mirrored triangles into quadrilateral cells
quads = []
total_neighbors = 0
for t in tris:
    if t.quad == None and t.other_half != None:
        quads.append(t)
        q = t
        q.corners = (q.corners[0], q.corners[1], q.other_half.corners[0], q.corners[2])
        q.quad = q
        q.other_half.quad = q
        q.all_neighbors.update(q.other_half.all_neighbors)
        q.all_neighbors.remove(q.other_half)
        q.all_neighbors.remove(q)
        total_neighbors += len(q.all_neighbors)

# clean up quads who still think they have triangles for neighbors
for q in quads:
    new_neighbors = set()
    for n in q.all_neighbors:
        if len(n.corners)==3:
            if n.other_half:
                if len(n.other_half.corners)==4:
                    new_neighbors.add(n.other_half)
        else:
            new_neighbors.add(n)
    q.all_neighbors = new_neighbors


# # adopt your other half's neighbors, minus them and yourself. mark other half as dead.
# for t in tris:
#     if t.other_half:
#         t.all_neighbors.update(t.other_half.all_neighbors)
#     t.all_neighbors.remove(t)
#     if t.other_half and t.other_half in t.all_neighbors:
#         t.all_neighbors.remove(t.other_half)
#     if t.other_half and not t.dead_half:
#         t.other_half.dead_half = True

pygame.init()
screen = pygame.display.set_mode(IMAGE_SIZE, 0, 32)
pygame.display.set_caption("Penrose Life")
pygame.display.flip()

paused = False
fast = False
randomize = True
found_oscillator = 0
randomized_tick = 0
tick = 0
timed_tick = 0
timed_tick_time = time.clock()
render_countdown = 0

history_length = 45
quad_history = [[0]*len(quads)]*history_length
quad_pointer = 0

myfont = pygame.font.SysFont("monospace", 15)
guidish = random.randint(0,99999999)

while True:

    tick += 1
    if tick - randomized_tick > 1000 and render_countdown == 0:
        randomize = True
    edited = False
    step = False
    if found_oscillator > 0 and render_countdown == 0:
        print "Potential p" + str(found_oscillator) + " osillator"
        render_countdown = found_oscillator
    if render_countdown == 0: # don't handle input while rendering an oscillator
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                sys.exit(0)
            elif event.type == pygame.KEYDOWN:
                # print event
                if event.scancode == 53: # escape
                    sys.exit(0)
                elif event.unicode == " ": # randomize
                    randomize = True
                    edited = True
                elif event.unicode == "p": # pause
                    paused = not paused
                elif event.unicode == "f": # fast
                    fast = not fast
                elif event.unicode == "s": # step
                    paused = True
                    step = True
            elif event.type == pygame.MOUSEBUTTONDOWN:
            # click to toggle a cell
                x = event.pos[0]
                y = event.pos[1]
                for q in quads:
                    poly = [(c.real,c.imag) for c in q.corners]
                    # http://www.ariel.com.au/a/python-point-int-poly.html
                    n = len(poly)
                    inside = False
                    p1x,p1y = poly[0]
                    for i in range(n+1):
                        p2x,p2y = poly[i % n]
                        if y > min(p1y,p2y):
                            if y <= max(p1y,p2y):
                                if x <= max(p1x,p2x):
                                    if p1y != p2y:
                                        xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                                    if p1x == p2x or x <= xinters:
                                        inside = not inside
                        p1x,p1y = p2x,p2y
                    if inside:
                        edited = True
                        q.state = 0 if q.state==1 else 1

    if randomize and render_countdown == 0:
        randomized_tick = tick
        randomize = False
        for q in quads:
            q.state = random.randint(0,1)
            edited = True

    if (not fast) or (tick%25==0) or edited or render_countdown > 0:
        # draw filled quads
        for q in quads:
            cs = [(c.real,c.imag) for c in q.corners]
            if __debug__:
                color = tuple(int(i*256) for i in q.debug_color)
            else:
                if q.state == 0:
                    color = (255, 255, 255)
                else:
                    color = (0, 0, 0)
            pygame.draw.polygon(screen, color, cs, 0)
        # draw edges
        for q in quads:
            if len(q.corners)==3:
                exit(1)
            cs = [(c.real,c.imag) for c in q.corners]
            width = 3
            pygame.draw.lines(screen, 0x7F7F7FFF, 1, cs, int(width))
        now = time.clock()
        speed = (tick-timed_tick)/(now-timed_tick_time)
        timed_tick_time = now
        timed_tick = tick
        screen.blit(screen, (0, 0))
        label = myfont.render("%4.2f/s"%speed, 1, (255,255,255))
        screen.fill(pygame.Color("black"), (0, 0, 110, 15))
        screen.blit(label, (0, 0))
        pygame.display.update()

    if __debug__:
        break

    if paused and not step and render_countdown == 0:
        #time.sleep(0.01)
        continue

    # screenshot
    if render_countdown > 0:
        filename = "oscillator_p%03d_%08d_%03d.png" % (found_oscillator, guidish, found_oscillator - render_countdown)
        pygame.image.save(screen,filename)
        render_countdown -= 1
        if render_countdown == 0:
            guidish = random.randint(0,99999999)
            found_oscillator = 0
            randomize = True
            continue


    # calculate new cell states based on the Game of Life rules
    # Edited by Scorbie to support arbitrary rules
    for q in quads:
        a = sum([n.state for n in q.all_neighbors])
        q.new_state = q.state
        # dead cells with three neighbors spawn
        if q.state == 0:
            q.new_state = 1 if a in RULE[0] else 0
        # live cells only survive with two or three neighbors
        else:
            q.new_state = 1 if a in RULE[1] else 0

    # update cell states
    for q in quads:
        q.state = q.new_state

    this_state = [q.state for q in quads]

    # don't bother checking
    if render_countdown == 0:
        # compare this board state to the last N-1 states
        for i in range(1,history_length):
            if quad_history[(quad_pointer-i)%history_length] == this_state:
                if i == 1 or i == 2: # stalled board or p2 oscillator (boring)
                    randomize = True
                    break
                #TODO: give up if the "oscillator" includes border cells
                #TODO: identify cases of two oprime oscillators overlapping
                elif i > 2:
                    found_oscillator = i
                    break # don't keep looking

        # remember this board state
        quad_history[quad_pointer] = this_state
        quad_pointer = (quad_pointer+1)%history_length

if __debug__:
    filename = "penrose.png"
    pygame.image.save(screen,filename)
    time.sleep(1)
 

Many rules look interesting. I wonder if there are any spaceships in any of the totalistic rules. I am also curious if some sort of Hashlife algorithm can be used here to simulate infinite grids. (By using the iterations to genreate a penrose tiling.)

[confocaloid]

[...]
I've also been looking at elliptic grids. The tetrahedron is just about trivial, and cube/octahedron/dodecahedron are quite quickly solved as well (where by "solved" I mean "determined the evolution of every pattern under every rule"); patterns either oscillate within their own symmetry group (eg. in B0/S4 or B14/S0, a cube with one face living makes a p4 oscillator) or reduce to a higher symmetry group. The icosahedron might support some interesting larger periods, haven't really investigated yet.
[...]

Suppose some cellular automaton is defined on the 20 faces of the icosahedron, with two cellstates ("dead" and "alive") and with some isotropic ruleset (the rules are the same for all cells and regardless of rotations/reflections).
What would be the highest possible period of an oscillator? What are all possible periods?
How many different periods of oscillators can coexist in a single CA of this type?
How many different oscillators can coexist in a single CA of this type?
Such questions should be answerable at least in principle (although might be unfeasible in practice), because there are only finitely many possibilities.

There are 2^20 different two-state patterns. With isotropic rules, it is enough to look at equivalence classes of patterns "up to rotations and reflections". I counted 9436 of those, which agrees with OEIS A252704.

Suppose the entire icosahedron is taken as the neighbourhood (i.e. the neighbourhood of any cell includes 19 other cells). Up to symmetries, I counted 176896 "essentially different neighbourhood configurations". (Question: Can anyone either confirm or correct this number?) Assuming that is correct, there are 2^176896 different isotropic rulesets (for every fully-specified cell condition, one can choose whether "the" cell will be alive or dead in the next generation). That is of course way too many to brute-force directly. Anything that requires generating and testing rulesets one-by-one is going to be unfeasible. Can this version of the question be answered with better algorithms?

Restricting to outer-totalistic rulesets only, there would be 40 fully-specified cell conditions (the cell's state can vary from 0 through 1 and the number of alive neighbours can vary from 0 through 19) and 2^40 different rulesets, which is still too many to generate and test directly. However, one could use a smaller neighbourhood that doesn't cover the entire icosahedron.

With a three-cell neighbourhood, there would be 8 fully-specified cell conditions (the cell's state can vary from 0 through 1 and the number of alive neighbours can vary from 0 through 3), 2^8 = 256 different rulesets, and at most 9436 * 256 = 2415616 "generate and evolve until it settles" iterations. This version of the question looks feasible to answer.

With a nine-cell neighbourhood, there would be 20 fully-specified cell conditions (the cell's state can vary from 0 through 1 and the number of alive neighbours can vary from 0 through 9), 2^20 different rulesets, and at most 9436 * 2^20 = 9894363136 "generate and evolve until it settles" iterations. This version of the question should be feasible with additional reductions/improvements.