The 4-way deterministic tiling problem is undecidable
It is shown that the (infinite) tiling problem by Wang tiles is undecidable even if the given tile set is deterministic by all four corners, i.e. a tile is uniquely determined by the colors of any two adjacent edges. The reduction is done from the Turing machine halting problem and uses the aperiodic tile set of Kari and Papasoglu. (c) 2008 Elsevier B.V. All rights reserved.
deterministic tiles tiling problem undecidability wang tiles domino problem