8
$\begingroup$

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$
1
  • 1
    $\begingroup$ Here's a related question with some references. $\endgroup$
    – t.b.
    Commented May 22, 2011 at 14:44

2 Answers 2

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .