TL;DR: Can anyone help me find a minimal set of triominoes that embed a universal computer?
This is not exactly about cellular automata, but it might be of interest to some of the same people (and you can embed 1-D cellular automata as an oriented tiling). I also don't claim to have any new ideas below. Some are definitely old, and some I may have rediscovered.
I had started to think about constraint systems involving mutually adjacent cells on a hex grid and their realization as a tiling, before noticing after a day or two that I had reinvented triominoes (more on that below).
I was originally interested in constraints that were fully symmetric up to rotations and flips, so the combination of colors assigned to the neighborhood would be independent of ordering. I was frustrated by any attempt to embed a universal computer this way and eventually realized why it is impossible: given two adjacent rows of colored hexes satisfying constraints, flip symmetry permits alternating these rows forever, so any 2-row tiling can be extended into a planar tiling. 2-row tilings are (roughly) equivalent to regular expressions, and therefore not universal.
The above observation was kind of a relief, because disallowing flips makes it easier to assign some kind of directionality. My goal is to avoid orienting the tiles by fiat like square Wang tiles (https://en.wikipedia.org/wiki/Wang_tile). I want a set of symmetric tiles that implement hex neighborhood constraints and impose their own orientation. After some trial and error, I found that this could be done with triangular tiles and that they basically match like triomonoes, though I use colors instead of numbers below. Here is an example of a tile set that imposes a (well-known, unique) 3-coloring of a hex grid.
Note that in this case, the constraints are flip-symmetric, but you need to put both the tile and its reflection in the set.
Here is another tile set that impose a (well-known) 4-coloring of a hex grid.
In this case, the constraints are not flip-symmetric, and the set consists of 4 triangular tiles.
Thinking in terms of embedding a 1-D CA in tiling constraints, I would like to impose a top-to-bottom orientation. I am not very happy with this result, because it requires 18 tiles and 9 "colors" (shown as colors and patterns). However, if you had a deterministic 1-D CA, you could use this to enforce predecessor/successor.
This gives a brute-force recipe for embedding a 1D CA that defines a next state based on the two states above it. You just take tiles representing the CA transition rules and form a cartesian product with the tiles above so that predecessor-successor rules always go no-dot/solid-dot/hollow-dot etc.
This is enough to show that you can embed a universal computer by tiling with a set of triominoes with rotations (details left as an exercise). However, it multiplies the set of transition rules by a factor of 18 just to impose an orientation. That's pretty clumsy.
I suspect there is a much small set of triominoes that implement a universal machine, and thus the tiling problem starting with a fixed initial placement is undecidable. Anyone have a reference to results in this area? I do understand that this is equivalent to Wang tiles. My main interest lies in the fact that they are triangular and that rotations are allowed.