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:
- wang tiles.png (108.9 KiB) Viewed 2095 times
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).
- hex tiles copy.png (208.21 KiB) Viewed 2095 times
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.
- examples.png (236.26 KiB) Viewed 2095 times
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).
