Conjecture of a subset of Wang tile which might be decidable

Question

From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:

The left color and right color do not uniquely determine the top color and bottom color. The tiles involved in practice in material science and physics for one big problem is actually more restricted and the tiling problem might actually turn out to be decidable.

So the subset of Wang Tile is lattice tiles, shown in my previous post:

Reference for Wang Tile

The general feature of the tile is that the pair (left color, right color) uniquely determine the pair (top color, bottom color).

I conjecture that a subset of Wang tiles which satisfies the restriction above might turn out to be decidable...

Any thought on this problem? Thank you.

Answer 1

It is a very nice question!

But I claim, unfortunately, that the tiling problem for your special kind of tile sets is also undecidable. Specifically, I claim that the ordinary Wang tiling problem reduces to an instance of your kind of tiling problem. That is, if we are given a finite list of ordinary Wang tiles $w_0,\ldots, w_n$, then we can create (according to a computable procedure I shall presently explain) a new set of tiles $t_0,\ldots,t_k$, such that the original set of tiles admits a tiling if and only if the new set admits a tiling, and furthermore the new set of tiles $t_i$ obey your deterministic property.

The new tiles are obtained from the previous tiles by annotating the labels on the original tiles. Given any Wang tile $w$, labeled with $1$ and $2$ on the left and right side, respectively,

                    -------------
                    |     3     |
                    |           |
           w   =    |1         2|
                    |           |
                    |     4     |
                    -------------

and for each tile $u$ with a label of $1$ on the right (so that it could legitimately form $uw$), we create a tile $t_{u,w}$ labeled by $(u,1)$, $(w,2)$ on left and right, respectively, and otherwise the same as $w$ on top and bottom. That is, we think of $(u,1)$ and $(w,2)$ as individual new colors in the new tile set.

                    -------------
                    |     3     |
                    |u         w|
   t_{u,w}   =      |1         2|
                    |           |
                    |     4     |
                    -------------

The meaning of the annotation is that the right-hand side label $(w,2)$ indicates $w$ and therefore contains all the information needed to know the top and bottom labels, and we add $(u,1)$ on the left simply so that it can match the corresponding new tiles corresponding to some $u$ that could match with $w$.

Thus, if $uw$ can be extended to a sequence $ruw$ in the original tiling, then $t_{r,u}t_{u,w}$ is legitimate in the new tiling. So any tiling of the plane using the original tiles can be transformed into a tiling using the new tiles. Conversely, if $t_{r,u}t_{u',w}$ is legitimate in the new tiling, then it must be that $u=u'$ becase the annotated labels match, and furthermore $uw$ is legitimate in the original tiling, since we only made $t_{u,w}$ when $uw$ was legitimate. So every tiling with the new tiles immediately produces a tiling using the old tiles. (Indeed, the tilings themselves are computable from one another.)

Finally, the new tiles obey your deterministic property, because the annotations on the side labels contain all the information necessary to determine the top and bottom labels. Indeed, the right color alone determines the top and bottom colors on these tiles, and severely restricts the possible left colors as well.

Answer 2

If you're interested in restriction of the domino problem to tile sets with some determinism properties, you might also be interested in this result about 4-way deterministic tile sets.