Wang tiles are (by Wikipedia): "equal-sized squares with a color on each edge which can be arranged side by side (on a regular square grid) so that abutting edges of adjacent tiles have the same color; the tiles cannot be rotated or reflected."
The usual decision problem associated with them is: given a set of tiles, can they tile the plane?
This problem is known to be undecidable and has a nice history (Wang originally gave a decision procedure, but it works only if the tiles form a periodic tiling, while there exists sets which give rise only to nonperiodic tilings). It has fascinated me personally for a very long time
The state-of-the-art proof of undecidability I'm familiar with is that of Raphael Robinson ("Undecidability and Nonperiodicity for Tilings of the Plane," Inventiones Mathematicae, 12(3), 1971 pp. 177–209). It is quite a difficult proof, and I have never seen it in textbooks.
I'm familiar with a much easier version - this time the set only needs to tile a quadrant of the plane, and the corner tile is already given. This problem is much easier to handle - the given corner tile enables us to "run a Turing machine" in the tiling (each row is a configuration) and undecidability follows. However, this result is primarily a "folklore" version - I don't recall it in textbooks at all.
This leads to my question: has Robinson's method been improved but remains folklore, and so not shown in textbooks? Is there a relatively simple proof of the undecidability of the general tiling problem I'm missing?
$\endgroup$ 12 Answers
$\begingroup$There's a newer proof given in "Two-by-Two Substitution Systems and the Undecidability of the Domino Problem", by Nicolas Ollinger. It seems to be available online at: . Hopefully, it is easier to understand than Robinson's proof.
$\endgroup$ $\begingroup$There is also the newer work of Kari "On the Undecidability of the Tiling Problem", which shows the undecidability of the domino problem by a reduction to the immortality problem for affine functions.
It shows the undecidability of the domino problem in the hyperbolic plane which was not shown by Robinson. I am not sure if it is easier than the proof by Robinson.
It is available here, page 74:
$\endgroup$
