ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Triominoes with rotations as universal Wang tiles

For discussion of other cellular automata.

Triominoes with rotations as universal Wang tiles

Postby pcallahan » May 17th, 2017, 2:20 pm

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.
Screen Shot 2017-05-16 at 12.08.51 PM.png
Screen Shot 2017-05-16 at 12.08.51 PM.png (55.88 KiB) Viewed 238 times

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.
Screen Shot 2017-05-16 at 12.28.02 PM.png
Screen Shot 2017-05-16 at 12.28.02 PM.png (51.69 KiB) Viewed 238 times

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.
Screen Shot 2017-05-16 at 12.38.30 PM.png
Screen Shot 2017-05-16 at 12.38.30 PM.png (103.67 KiB) Viewed 238 times

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.
pcallahan
 
Posts: 67
Joined: April 26th, 2013, 1:04 pm

Re: Triominoes with rotations as universal Wang tiles

Postby simsim314 » May 19th, 2017, 3:22 pm

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).
User avatar
simsim314
 
Posts: 1487
Joined: February 10th, 2014, 1:27 pm

Re: Triominoes with rotations as universal Wang tiles

Postby pcallahan » May 21st, 2017, 12:31 pm

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).

Screen Shot 2017-05-21 at 9.32.36 AM.png
Screen Shot 2017-05-21 at 9.32.36 AM.png (12.56 KiB) Viewed 141 times


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.

Screen Shot 2017-05-21 at 9.12.06 AM.png
Screen Shot 2017-05-21 at 9.12.06 AM.png (12.28 KiB) Viewed 141 times


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

? U    ?    ?    ...    ?
? S_i1 S_i2 S_i3 ... S_in ?


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.
Last edited by pcallahan on May 21st, 2017, 3:26 pm, edited 19 times in total.
pcallahan
 
Posts: 67
Joined: April 26th, 2013, 1:04 pm

Re: Triominoes with rotations as universal Wang tiles

Postby pcallahan » May 21st, 2017, 12:38 pm

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?
pcallahan
 
Posts: 67
Joined: April 26th, 2013, 1:04 pm

Re: Triominoes with rotations as universal Wang tiles

Postby pcallahan » May 21st, 2017, 1:01 pm

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.
pcallahan
 
Posts: 67
Joined: April 26th, 2013, 1:04 pm

Re: Triominoes with rotations as universal Wang tiles

Postby simsim314 » May 22nd, 2017, 12:24 pm

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.
User avatar
simsim314
 
Posts: 1487
Joined: February 10th, 2014, 1:27 pm

Re: Triominoes with rotations as universal Wang tiles

Postby pcallahan » May 22nd, 2017, 11:58 pm

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:
Screen Shot 2017-05-22 at 8.40.21 PM.png
Screen Shot 2017-05-22 at 8.40.21 PM.png (11.75 KiB) Viewed 83 times

Transform it to colored triominoes with rotations allowed (but no flips):
Screen Shot 2017-05-22 at 8.40.30 PM.png
Screen Shot 2017-05-22 at 8.40.30 PM.png (60.73 KiB) Viewed 83 times


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.
pcallahan
 
Posts: 67
Joined: April 26th, 2013, 1:04 pm

Re: Triominoes with rotations as universal Wang tiles

Postby simsim314 » May 23rd, 2017, 3:02 am

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:

Initial.png
Initial.png (8.14 KiB) Viewed 71 times


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:

RuleDef.png
RuleDef.png (7.07 KiB) Viewed 71 times


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:

FullStep.png
FullStep.png (7.41 KiB) Viewed 71 times


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.
User avatar
simsim314
 
Posts: 1487
Joined: February 10th, 2014, 1:27 pm

Re: Triominoes with rotations as universal Wang tiles

Postby simsim314 » May 23rd, 2017, 4:52 am

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.
User avatar
simsim314
 
Posts: 1487
Joined: February 10th, 2014, 1:27 pm


Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 5 guests