The 4-way deterministic tiling problem is undecidable

AbstractIt 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