# Decidability of tiling of $\mathbb{R}^n$

Given a polytope of dimension $n$, is there some general way to determine if it can tile $\mathbb{R}^n$?

-
This is related to mathoverflow.net/questions/53515/decidability-of-tiling-r2 . –  Grumpy Parsnip Jan 27 '11 at 23:27

The book Tilings and Patterns by Branko Grünbaum and Geoffrey Shephard (W.H. Freeman) is still, despite its 1987 publication date, an excellent source of information about tiling questions. Wang tiles and decidability problems are treated in Chapter 11.

-
Hello, Joseph! Do they prove or mention that the tiling problem is undecidable for the case of inputs consisting of just one tile? (-Joel) –  JDH Jan 27 '11 at 19:32
@Joel- No they don't prove this. As I understand the issues here there are many variant questions depending on the rules that one insists on the tiles obeying. –  Joseph Malkevitch Jan 28 '11 at 13:02

Edit 3/14/2013: My original answer below was confusing "undecidability" with "independence from the axioms of set theory," and I want to preface it with my revised, hopefully more accurate understanding.

At one point in time, it was open whether or not there exists a Turing machine which could decide if a given set of tiles would tile the plane. Then Hao Wang showed that this problem was indeed decidable if and only if every set of tiles that could tile the plane could do so periodically. Wang's student Berger, and later others like Penrose demonstrated the existence of aperiodic sets of tiles, thus proving via Wang's result that the tiling problem is undecidable. (No Turing machine could reliably spit out a yes-no answer, given a set of tiles.) For a long time it remained open whether there was a single tile that could only tile aperiodically. (Penrose had gotten it down to 2. Berger had started with about 20,000 I think.) But then in 2010 the Taylor-Socolar tile was discovered. It is a single disconnected tile which tiles the plane but only aperiodically. I've included a picture.

This does not directly address the OP, but is suggestive that it could be an undecidable problem.

Original post: Probably there is not! Indeed I believe there is a single (very complicated) 2D tile for which the problem of whether it tiles the plane is logically undecidable [Edit: meaning independent of the axioms of ZFC set theory]! I don't have the reference handy. Perhaps somebody else can supply it. With a quick Google search, the Wikipedia article on Wang tiles is the closest I could come. Wang tiles are presented as colored tiles where the colors have to match on shared edges, but these can be converted to regular tiles by modifying the boundary so that only like colors can join. According to Wikipedia, there is a set of 13 tiles for which the tiling problem is logically undecidable [Edit: meaning independent of the axioms of ZFC set theory], but I seem to recall hearing that this number has been reduced to 1, but possibly no longer in the Wang tile category.

Edit: As was pointed out to me in the comments, this seems different than asking whether the tiling problem is decidable in the decision problem sense, for which the truth of any finite proposition is assumed to be known, and the question is whether an algorithm exists that successfully runs on the set of all tiles.

-
I am fascinated if there is a single finite tile, such that the question of whether it tiles the plane is independent of PA or some other standard axiomatization. Can you provide a reference? But I note that this observation by itself doesn't actually answer the decidability question about all tiles. That is, can you move from one logically independent instance to undecidability of the general problem? –  JDH Jan 27 '11 at 13:01
Probably I'm missing something, but if you can't decide whether a particular set of tiles tesselates the plane, then there is no algorithm which can, given an input of tiles, decide whether they tile the plane, because that algorithm would provide a solution to the particular instance for which there is provably no solution. –  Grumpy Parsnip Jan 27 '11 at 13:46
I hope someone else knows the single-tile result and can provide a reference. –  Grumpy Parsnip Jan 27 '11 at 13:47
The point is that a single instance has a single yes/no answer, which is certainly computable. If the ability to tile is independent of ZFC, say, then this just means that in some models of set theory it can tile and in others it cannot, but in each of these models, there is a definite answer. Another way to say it: a decision problem is the problem of deciding membership in a set (of natural numbers, viewed as representing tiles, say), but all finite sets are definitely decidable. –  JDH Jan 27 '11 at 14:41
@JDH: It could be. Both questions are interesting! –  Grumpy Parsnip Jan 27 '11 at 15:17

The non-existence of an algorithm (for the plane) can be found in a paper by Adler and Holroyd, Geometriae Dedicata, 1981. The proof uses a straightforward simulation of Wang tiles.

-
The proof I know shows that the tiling problem for a finite set of tiles is undecidable, first by reducing the Wang tiling problem, which reduces the halting problem and hence is undecidable. But does your reference show that the tiling problem for input having one tile is also undecidable? –  JDH Jan 27 '11 at 15:18
The 1981 Geometriae Dedicata paper does not show undecidability for 1 tile. –  André Nicolas Jan 27 '11 at 15:40