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?

  • 1
    $\begingroup$ Here's a related question with some references. $\endgroup$ – t.b. May 22 '11 at 14:44

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: http://hal.inria.fr/docs/00/26/01/12/PDF/sutica.pdf. Hopefully, it is easier to understand than Robinson's proof.


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: https://link.springer.com/content/pdf/10.1007%2F978-3-540-77566-9.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.