Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

Conjecture of a subset of Wang tile which might be decidable

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.

user40780
  • 867
  • 4
  • 16