Given a polytope of dimension $n$, is there some general way to determine if it can tile $\mathbb{R}^n$?
Decidability of tiling of $\mathbb{R}^n$
-
1This is related to http://mathoverflow.net/questions/53515/decidability-of-tiling-r2 . – 2011-01-27
3 Answers
Edit 9/30/2015 My revised understanding is still not correct! The undecidability of the tiling problem is not equivalent to the existence of an aperiodic tiling. See Edmund Harris's answer at this related MO post.
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.
-
1I 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? – 2011-01-27
-
0Probably 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. – 2011-01-27
-
2I hope someone else knows the single-tile result and can provide a reference. – 2011-01-27
-
0The 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. – 2011-01-27
-
0@JDH: I have been using "undecidable" to mean "independent of ZFC", whereas you are using it to only apply to the existence of algorithms for decision problems. I see that both usages occur in the literature, which I see has caused some confusion in our discussion. – 2011-01-27
-
1Yes, the term "decidable" is used in these two different ways in logic. But I interpret the question here to be about the computability sense of decision problem. – 2011-01-27
-
2@JDH: It could be. Both questions are interesting! – 2011-01-27
-
0@JDH: Also thanks for clarifying my confusion. I'd never dwelt on the fact that these two notions of undecidable are quite different. I just had the vague idea that an algorithm was a ZFC object so that the nonexistence of a ZFC proof would imply the nonexistence of an algorithm. But maybe the distinction is that we only ask for the existence of an algorithm, not a ZFC proof that the algorithm is correct? – 2011-01-27
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.
-
1The 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? – 2011-01-27
-
1The 1981 Geometriae Dedicata paper does not show undecidability for 1 tile. – 2011-01-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.
-
0Hello, Joseph! Do they prove or mention that the tiling problem is undecidable for the case of inputs consisting of just one tile? (-Joel) – 2011-01-27
-
0@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. – 2011-01-28