ConwayLife.com

I'm not sure if this is new or interesting, but it came up recently when I was looking at tilings of hexagons with matching sides analogous to Wang tiles. I am interested in tiles that are free to rotate (unlike Wang tiles ) in the hope that some surprising self-orientation will emerge. This does not really happen in an interesting way with rule 110, but it is a useful illustration of the expressive power of such tilings (note: it does not prove any new universality results, since all of these systems are known to be universal).

First off, it is pretty easy to see that rule 110 can be implemented as a conventional Wang tiling, and I'm sure this is not new. It can be done with 6 tiles total. A simple construction is to begin by writing the transition between rows of rule 110 as a finite state automaton. Since rule 110 is a function from a window of three input bits to a single output bit, the two leftmost bits can be stored as the state. That suggests 4 states: 00?, 01?, 10?, 11?. However, if the middle bit is 0, the left bit is ignored, so there are really 3 states: ?0?, 10?, 11?. Each transition between states is associated with a bit in the row above and another bit in the row below. The top bit is identical to the middle window bit, The resulting FSA is non-deterministic and the transitions can be associated with Wang tiles: An analogous tiling can be realized with hexagons colored to constrain neighborhoods in a shifted hexagonal grid. This is easier to illustrate than explain (shown below). In this case, we have 10 tiles. Four of them map pairs of adjacent bits (black or white) to states (green, blue, or red). Six of them map state transitions to the resulting bits. The hex tiles can be rotated, unlike the Wang tiles, but not flipped in a mirror image. They must be joined along matching sides (including the interior gray boundary, which must also match). Though the hexes can be rotated, it is easy to see that if a row of hexagons is placed in the plane with only black and white top rhombuses, then the next row must all have green, blue, or red rhombuses at the top, and so on alternating. So it implements rule 110 deterministically with such an initial state (It is actually possible to assign any initial state including one without a rule 110 predecessor, and complete the tiling above; proof left as an exercise).

A more interesting question is what kinds of patterns emerge when no orientation is imposed initially. To answer that I implemented a crude simulated-annealing style algorithm to color a periodic hex grid using the associated constraints without preference to any direction. I don't think the results (below) are very interesting, but there is a certain structure to them. The green and white hexes follow the rule that no neighborhood can have all the same color. These wind up covering a large part of the generated pattern, with other colors clustering in islands according to the other constraints. Some constraints don't show up (or very rarely) such as two black and a red, or two red and a white. I have not explored the space of such tilings with 3 colors. I also cannot see how to embed rule 110 with fewer than 5 colors, but I suspect there may be some interesting looking tilings with 3 or 4 colors. Even 2 colors admits a realization of an XOR function and the construction of Sierpinski triangles. The green-white 2-tile subset in the image above is also a little interesting and can be related to tilings by rhombuses (left as an exercise; or I will explain in a followup if anyone is interested).

pcallahan wrote:...
The green-white 2-tile subset in the image above is also a little interesting and can be related to tilings by rhombuses (left as an exercise; or I will explain in a followup if anyone is interested).

Am I anyone?

In math logic, there are proofs for establishing relationship between Tiling problem and Turing machines. Hoping that the same ideas can be reused as well.

Naszvadi wrote:In math logic, there are proofs for establishing relationship between Tiling problem and Turing machines.

Thanks. Yes, that's what I meant when I said "all of these systems are known to be universal." It is hard NOT to find systems that are universal, or equivalent to Turing machines, though (e.g. with rule 110) it may be quite a challenge to prove.

Universality aside, I am looking for tiling and constraint systems that generate interesting looking patterns (a very subjective criteria I realize). Ideally, and this is really subjective, the result should be a set of tiles that is fun to assemble by hand, though I usually do this with a combination of custom software and Google docs drawing app.

Since you are "anyone" (not to mention someone in particular) here is a proof by picture of the relationship between rhombic tilings and hex grids colored with the constraint that no neighborhood of 3 mutually adjacent hexagons all have the same color. To get the rhombic tiling, just draw a center-to-center line between adjacent hexagons with opposite colors (This actually drove me crazy for a few weeks before seeing the connection that seems obvious in retrospect. Tiling rhombuses is equivalent to bipartite matching, the same way tiling dominoes on a chessboard is, so there are very fast algorithms for generating random tilings like the above or ones with additional constraints).