ConwayLife.com

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.

I think you have two different definitions you're working with, which are a bit confusing.

The question is what you're looking for: possibility of universal computation, or that every valid tiling would be aperiodic?

Because first you write:

pcallahan wrote: 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.

This is correct, but here you're talking about the option of making some tiling which is not aperiodic. But you don't show that every possible tiling is not universal, just that there exist an infinite subset of periodic tiling.

Then you go on talking about simulating 1D rules, which is cool idea - but I don't think there exist any 1D rule which has no infinite subsets of "trivial" periodic patterns.

So I'll bring you to the initial question: can you prove that there is no way to avoid directionality, and still get a universal constructor. The existence of infinite periodic subset, in no way proves the absence of universal computation, it only proves that you could at any given point make it "trivial", but "trivial" patterns exist also in the case of any 1D CA.

---

Another small nuance is that you can simulate only reversible 1D CAs, because if the CA is not reversible you can't always get tiling in both direction from the initial state (or at least you could only simulate reversible states in this CA and not all states).

This brings me to another question which bothers me: how can you talk about universal computation, while you're talking about tiling. Tiling is one single 2D state, computation on the other hand is process in time. I see that they are equivalent, yet I can't call tiling a "true" computation, it's more like capturing a movie of a true computation, and not computing it (but this indeed a matter of definitions).

First off, thanks for reading my posting! I agree that my explanation isn't as clear as it should be, but I can answer most of your objections.

I'm not really interested in forcing aperiodic tilings. I accept that any tile set of interest may admit periodic tilings. In fact, I would normally have a notion of a "blank" value and tiling the plane with blanks will always be possible.

What I am interested in forcing are the infinite extensions of certain finite tilings. My claim is that you can easily embed a 1-D CA as the extension of a subset of initial finite tiles. They do not have to be reversible either, though I understand how it might look that way.

Start with my oriented tiling (3rd one with 18 tiles). Assuming I don't have anything wrong (please correct me if so), then any downward triominos will have one of these forms with varying colors (nine possible).
These are the only neighborhoods I'm actually interested in constraining (to explain below).

Let's digress for a minute into pure 1-D CA. We have a CA with m-states, and each next state is a function of the 2-cell neighborhood consisting of the cell and its right neighbor. (Note that information propagates exclusively to the left in such a rule, but we can just shift our window of interest.)

(1) We agree (?) that for sufficiently large m, there is such a CA that supports universal computation.

(2) For technical reasons, we would like the CA to be robust to arbitrary values outside a fixed window of adjacent cells. E.g., a row like ....??????????00002487284782742390000'''???????????.... should have the same final state inside some window of interest independent of how we assign '?' values. See appendix (bottom of post) for how to do that by extending the known region with each step.

(3) There is a special state S_m = "UNKNOWN" (not to be confused with blank), for which we introduce the one non-deterministic rule in our CA, namely (UNKNOWN, UNKNOWN) -> S_i for all m. UNKNOWN is never a successor state except if its predecessors are both UNKNOWN.

To implement the above CA, we begin by introducing downward triominoes as follows. For each transition rule (S_i, S_j) -> S_k where i,j,k<m (i.e. not UNKNOWN) we add nine triominos <S_i,S_j,S_k*> <S_i*,S_j*,S_ko> <S_io,S_jo,S_k> (marked * and o to indicate circle symbols and with all allowed colorings) For all i, we add triominos <UNKNOWN, UNKNOWN, S_i> with all allowed circles and colorings . (Note that no tiling is possible in which UNKNOWN is left-right adjacent to a value other than UNKNOWN on the same row.)

We allow all possible combinations of states for upward triominoes that obey the coloring rules. It is trivial to observe that once downward triominoes are placed, the values of upward triominoes are determined, so we don't try to use them for constraints.

Now we simply encode the initial state S_i1, S_i2, ..., S_in as a row of downward triominoes colored by repeating this pattern.
We can find the appropriate triominoes in the transition set we constructed above. Note that you have to repeat the state in adjacent triangles.

Above Si1 on this row, we place a single (UNKNOWN, UNKNOWN) -> Si1 downward triangle colored appropriately.

I.e.:
The triominoes introduced above (again, correct me if I am wrong) force any tiling to have a row of U values, force all rows above them to be U, allow some way of filling in the first, partially filled row, and enforce CA rules on all successive rows.

Note that "U" values eliminate the need for a reversible automaton. There is a well-defined initial state. The trick of the 9-coloring is to enforce a "times arrow" without which it really does get tricky to have non-reversible successor rules, but with it, there is a simple (if clumsy) construction. To repeat, one reason the tiling can be completed like this is that we do not limit the upward triominoes at all. So all constraints follow directly from CA transition rules.

This brings me to another question which bothers me: how can you talk about universal computation, while you're talking about tiling.

Well, it comes down to what bothers you, since you agree (I think) that the systems are isomorphic. I am not sure why you think of a deterministic Turing machine as "computation" in this sense when its entire future is predetermined from the initial state. Whether we view this as a dynamic or static system is a matter of convenience. I don't see how you would make the distinction mathematically. Tiling is also a dynamic process in practice, because you cannot make one without calculating the position of the tiles as you go (assuming no closed-form solution.)

------
Appendix: How deal with arbitrary values outside the initialized area of the CA

We can introduce two new states L (left boundary) R (right boundary). Assume there is a "blank" state B and we want the CA to behave as if it was initialized with blank at all positions left and right of the initialization window.

We add the following transition rules (S_i, L) -> L and (R, S_i) -> R for all i from 1 to m. We also add rules (L, B) -> B and (B, R) -> B. We begin the initialization window with states L, B and end it with B, R. For all subsequent generations, the successors of the initially defined states are identical to a surrounding the initialization window with B states.

This is a very brute force approach, and I expect that smaller CA rules would enforce this condition naturally.

This is correct, but here you're talking about the option of making some tiling which is not aperiodic. But you don't show that every possible tiling is not universal, just that there exist an infinite subset of periodic tiling.

This was not addressed in my previous posting, but my (generalized) claim is that with any initial placement of a finite number of triominoes from a flip-symmetric set, there is either a finite disproof that the tiling be extended, or if it can be extended, this extension can be completed with alternating rows. Do you disagree with this?

Finally, my suspicion is that throwing away all the awful gadgets for enforcing CA directionality and starting with some small sets of rotationally symmetric triominoes, we may find interesting tilings that admit universal computation in a more natural sense and don't force the directionality in an arbitrary way (which classical Wang tiles do). Why is this interesting? I think it is, but you're free to disagree.

What I imagine is a set of symmetric triominoes such that a "seed crystal" (initial placement) will impose constraints on the rest of the plane that are aperiodic and potentially undecidable. Assuming there is no fatal error in the more detailed construction I posted, one can certainly ask undecidable questions about completing inital placements of rotationally symmetric triominoes from a sufficiently large set. But the construction requires many states and imposes a direction by design. I would like to see the direction arise naturally from as few constraints as possible. I would also like to avoid enforcing the same direction over the whole plane the way the 18-triomino basis does.

OK your formulation of extensibility is reasonable. Although notice that in case of tiles there could be few extensions, so although finding specific extension might be reducible but finding all extensions might require universal computation. I can definitely accept your definition of finding at least one extension, might be as complex as universal computation.

Here is my take on the issue:

You can see that actually you have a row of hexagons. Two hexagons can force a color of the third in next row. So the question can be reduced to the following:

Assuming we have initial state row: x1, x2, ..., xn, and a rule which works on pairs of X(i), X(i+1) -> Y(i), what is the minimal number of states, to have universal computer? To make it symmetrical we can also require each rule of type
(a, b)->c to be "transitive" i.e. if (a, b) -> c then: (a, c)->b and (b, c) -> a if you want the tiles to be flippable then we also need to request: if (a, b) -> c then (b, a) -> c. In other words a rule is just a set of triplets.

How many such rules exist per specific number of states? I'm not sure, but it looks to me for high enough states this will generate universal computation. I see how to make 32 tiles with 8 colors:

If we use 4 colors, each hexagon can be assign to two bits. Now we can use regular 2 state automaton, a pair of two bits are corresponding to 4 bits. 4 bits generate 2 bits result, i.e. single color out of 4.
Now the only thing we need is to solve the symmetry issue. This can be done by adding (0', 1') states for even and odd rows. Each even row of (0, 1) bits will generate (0', 1') row, and the opposite. So this is a duplication of the same rule and states, reaching 8 states and 32 rules i.e. tiles.

For two colors we get single possible rule XOR. So this is a question that should be answered by running few simulations on possible rules. I think directionality is artificial, so somewhere around 5 states should generate complex enough behaviour.

I think the next would be to write some script to generate all rules per number of states.

With a little work, it should be possible to force a unique extension from partial tilings that meet certain conditions (on a row with left-right boundary states and an UNKNOWN value above). Instead of tiling the region outside the boundaries with arbitrary successor states, it could be made uniform. E.g., with a left-of-left state such that only (LL,LL) and (LL,L) adjacencies have tiles and a right-of-right state such that only (RR,RR) and (R, RR) adjacencies are allowed.

I would like to write some code to explore small triomino sets, but it's a little more work than I have time for right now.

Finally, another route to a universality proof is just to reduce triominos with rotations to classic Wang tiles (https://en.wikipedia.org/wiki/Wang_tile) with fixed orientation. There might be a simpler construction, but I think this works.

Given a Wang tile t with fixed orientation and edge colors a, b, c, d: Transform it to colored triominoes with rotations allowed (but no flips): So given a collection of n Wang tiles, you can construct a set of <18n triominoes. These are free to rotate, but can only fit together to form Wang tiles as above (counterexamples welcome). This construction eliminates anything interesting about using triominoes, but it should also eliminate any concerns about whether they are equivalent in power to Wang tiles.

Addendum: You might wonder why I don't use edge-matched triangles, which I suspect would have an easier transformation to Wang tiles. Well, my original interest was in coloring a hex grid based on constraints of mutually adjacent hex cells. This is isomorphic to triomino matching. I am not sure if it is intrinsically simpler or more interesting than edge-matched triangles, but I have just gotten interested in it.

I would keep working with rectangular tiles an show the equivalence to CA.

I've found how to code any two states 1D CA with 8 tiles, and 6 colors.

Lets say we have initial state, we can code 0, 1 with RED and BLUE:
Now we need extra 4 colors to define the following situations:

My color | Right Color | Left Color | Color Index
RED | RED | X | 1
RED | X | RED | 1
BLUE | BLUE | X | 2
BLUE | X | BLUE | 2
RED | BLUE | X | 3
BLUE | X | RED | 3
RED | X | BLUE | 4
BLUE | RED | X | 4

For example:
Now in total we have 8 situations of neighbor setup (2 in power of 3) or 256 bits of a rule. So we only need 8 tiles.

For example:
EDIT There is one limitation on the rule set:

if (1,0,1) -> 1 then we get a tile that can replace input and output, and we get (0,1,0)->0 using 7 tiles.
if (1,0,1)->0 then we must use 8 tiles and a rule where (0,1,0)->1 to avoid symmetry.

So in practice we get only 128 rules, and rule 110 and 90 are not part of them but rule 30 is. So I'm not sure it's universal computer, but it's definitely aperiodic and probably undecidable.

Now I see that if we use 4 colors, RED-BLUE (0,1) and SAME-DIFFERENT neighbor and constrain the rules, we get aperiodic extension with only 4 tiles (although aperiodic extension of CA is not the same as simply aperiodic).

It's quite simple to code rule 150 into 4 such tiles (there is also rule 105 with 5 tiles).

Specifically (S for same, D for different):

S,1,S,0
D,1,S,1
D,0,S,0
D,1,D,1

EDIT I wonder can we get, using this approach, a more intuitive "true" wang tile set.

EDIT2 Although rule 105 and 150 considered class 3 rules, they might still contain universal computation. Class 3 only means the tendency to fall into chaos, we know of 2d rules with similar tendency like s0/b2 which contains ships and other interesting stuff.

EDIT3 Rule 150 is definitely not universal, because it can be computed using a linear function of the input, as its transform can be mathematically reduced to: (l,v,r) -> (l + v + r) % 2, basically any Nth generation is linear function of the input. The same is true for rule 105 which is the dual case: (l,v,r) -> (l + v + r + 1) % 2

EDIT4 But this is interesting fact that tile completeness is turing complete. I wonder what is the next step of this realization? Finding minimal tiling set which can be used for coding?

EDIT5 I would suggest to use the following definitions:

Definition: Codable tiling

It's a tiling set where given an initial partial tiling of a plane (called a tape), follows the following rules:

1. The extension of a tiling can be done in only one single way for any partial plane cover.
2. The extension of a tiling is turing complete problem.

The question is what is the minimal tiling set (in number of colors and tiles), to generate codable tiling.

I am actually interested in triominoes in particular right now, though obviously there are many ways to embed computation or undecidable problems (however you want to think of it) in tiling systems.

I thought this set of triominoes was interesting enough to print and cut out, though I very much doubt there is any undecidable problem associated with it. It does enforce some interesting properties: tricolor paths that separate regions of two other colors. If the paths are closed, they have to be a multiple of three in length. Isolated hexes are also possible, but not any longer paths with a dead end. The three-color triominoes always have to attach to each other as shown, so they are left uncut as rhombuses.

This 5-color 10-tile triomino set has some interesting properties, though it fails my original desiderata on two counts. I doubt it is universal, and it is not amenable to applying local rules: you get in trouble fast if you just start placing tiles. I had to use exhaustive search to get the examples below. I did get some larger "almost" solutions with a kind of simulated annealing.

I found this set in an enumeration, but the simplest "explanation" is to begin with the four triominoes without any red (these tile by themselves as a periodic 4-coloring of hexes). Then any other color can be replaced by red in one, but not two places, to form the other tiles. Note that red is only needed where the yellow-white path turns, so I prefer blue or green when possible. You get the same structure either way; it could be added as a constraint by forming composite tiles, but I want to stick to triominoes, my current obsession. Placement with periodic boundaries. Placement with free boundaries.

This is more along the lines of what I have been looking for, but I had to apply some thought to it instead of searching blindly. This is a 12-triomino set with 6 colors: red, green, blue that are either dark or light. Clockwise red-green-blue triominoes (top row, shown pointing up) have either 0 or two light colors. Counter-clockwise red-green-blue triominoes (bottom two rows, shown pointing down) may have any combination of light and dark colors (of which there are 8 ). This choice of tiles forces a 3 coloring of the resulting hexes and partitions triangles into "up" and "down" neighborhoods (which may be at any orientation as long as they are consistent). The "down" triangles are unconstrained except for the 3 coloring, while the "up" triangles realize a constraint on the additional colors (in this case two: light and dark).

The result is not universal. It is basically an XOR automaton (e.g. from bottom to top), but it makes some nice Sierpinski-like patterns. Here's an example: By putting constraints on only the clockwise triangles, it is easier to embed functional rules without over-constraining. The counter-clockwise triangles are already constrained by their neighbors. We can omit the counter-clockwise tiles entirely by using hex tiles instead of triominoes to fill in the gaps. In fact, you no longer need the three coloring with the hex tiles and may simply use two colors for the XOR'd values (left as an exercise). This makes me think that I may be more interested in finding hex tiles like the above that represent constraints on only the "up triangle" neighborhoods.

I'm not entirely sure. On the one hand, any approach to realizing a CA with triominoes that leaves half the neighborhoods unconstrained would require tiles for all possibilities (e.g. the 8 triangles above, and in general k^3 for some k). This gets unmanageable for k > 2 (I would like a set that is suitable for tiling by hand). On the other hand, trying to constrain the "up" and "down" neighborhoods with the same set of triominoes makes it hard to force the direction of the constraints. You get some interesting tilings, but nothing like a CA. It is possible that a tile set exists that naturally divides into up and down triominoes without having to force it with a 3-coloring as above.