Decidability of tiling R^2 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:09:18Z http://mathoverflow.net/feeds/question/53515 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/53515/decidability-of-tiling-r2 Decidability of tiling R^2 fastforward 2011-01-27T17:44:12Z 2012-05-13T13:24:04Z <p>Does there exist a closed curve, with finite area and finite circumference, of which it is undecidable (in an axiomatic system where it is constructable) whether it can tile the plane?</p> <p>I know the general problem of a set of polygons is undecidable, but I haven't found any information on the single tile case.</p> http://mathoverflow.net/questions/53515/decidability-of-tiling-r2/53516#53516 Answer by ARupinski for Decidability of tiling R^2 ARupinski 2011-01-27T18:02:19Z 2011-01-27T20:20:37Z <p>Isn't this question equivalent to the Heesch Problem of determining how much of the plane can be tiled by a given single tile?</p> <p>See <a href="http://math.uttyler.edu/cmann/math/heesch/heesch.htm" rel="nofollow">http://math.uttyler.edu/cmann/math/heesch/heesch.htm</a> for examples.</p> http://mathoverflow.net/questions/53515/decidability-of-tiling-r2/53517#53517 Answer by Ricky Demer for Decidability of tiling R^2 Ricky Demer 2011-01-27T18:32:38Z 2011-01-27T20:56:28Z <p>Yes.</p> <p>Define the Jordan curve C by "(the Continuum Hypothesis is true and C is the counterclockwise path onto the unit square which starts at $\langle 0,0\rangle$ and has speed everywhere equal to 1/4) or (the Continuum Hypothesis is false and C is the counterclockwise path onto the unit circle which starts at $\langle 1,0\rangle$ and has speed everywhere equal to $\frac1{2\cdot \pi}$)".</p> <p>Then it is undecidable in ZFC whether C can tile the plane. <br><br><br> EDIT: <br> Now, perhaps you could say what you <em>do</em> mean by "constructable in the same axiomatic system which it is undecidable", since I am completely stumped.</p> http://mathoverflow.net/questions/53515/decidability-of-tiling-r2/53547#53547 Answer by Nick S for Decidability of tiling R^2 Nick S 2011-01-27T23:00:09Z 2011-01-27T23:00:09Z <p>If I remember right any Turing machine can be translated into a set of Wang tiles, so that the tiling problem for this set of tiles is equivalent to the decibility of the turing machine.</p> <p>Assuming the non-existence of an aperiodic set of tiles, Wang provided the Decidability of any tiling problem in R^2. Since this is not possible, it basically proves the existence of aperiodic tiles.</p> <p>So the general decidability problem turned out to be equivalent to the non-existence of an aperiodic set of tiles , which suggests that the decidability problem for 1 tile might be equivalent to the non-existence of an aperiodic 1 tile. I wonder if the Wang theorem can be changed to prove this, could be a starting point.</p> <p>Such a tile is called an Eistein tile, and if I remember right the problem of its existence was open until few months ago, but it was reported recently that one was found...</p> http://mathoverflow.net/questions/53515/decidability-of-tiling-r2/76099#76099 Answer by Edmund Harriss for Decidability of tiling R^2 Edmund Harriss 2011-09-22T01:11:28Z 2012-05-13T13:24:04Z <p>The answer by Nick S is essentially correct, but I can provide a little more detail.</p> <p>It is not hard to show that the tiling problem (if a set of shapes admits a tiling of the plane) is decidable if every set of shapes that tile admit a periodic tiling. The algorithm is to put shapes together, look at the way two shapes can combine, 3 shapes and so on. If the shapes cannot tile you will eventually find a ball that cannot be covered, if they can tile periodically you will eventually find the patch that can go periodic. </p> <p>The discovery of aperiodic tilings and the result that the tiling problem was undecidable were proved at the same time by Berger. In fact Berger used an aperiodic tiling to show that the tiling problem was undecidable (originally in his thesis). Note that he (and others) call it the "domino problem", as the question was originally posed for squares with coloured edges, called Wang tiles.</p> <p>R Berger The undecidability of the domino problem<br> <em>Mem. Amer. Math. Soc.</em> <strong>66</strong> 1966<br> <a href="http://books.google.com/books/about/Undecidability_of_the_Domino_Problem.html?id=8AmiHD0Lbu8C" rel="nofollow">http://books.google.com/books/about/Undecidability_of_the_Domino_Problem.html?id=8AmiHD0Lbu8C</a></p> <p>Berger's proof was significantly simplified by Rafeal Robinson. An important part of the simplification was considering a smaller set of aperiodic tiles. Berger's example required 20,426 tiles, whereas Robinson's required just 6. </p> <p>R M Robinson, Undecidability and Nonperiodicity for Tilings of the Plane<br> <em>Inventiones math.</em> <strong>12</strong> 177-209, 1971<br> <a href="http://www.lif.univ-mrs.fr/~fernique/qc/robinson.pdf" rel="nofollow">http://www.lif.univ-mrs.fr/~fernique/qc/robinson.pdf</a></p> <p>Although it proved useful in these proofs, the existence of aperiodic tilings is not equivalent to the undecidability of the tiling problem. For one thing, by definition, the tiling problem is decidable for all known aperiodic tilings. The best case for the tiling problem is a result of Nicolas Ollinger. He shows that the tiling problem is undecidable for sets of 5 tiles using a construction based on polyominoes. </p> <p>N Ollinger, Tiling the Plane with a Fixed Number of Polyominoes.<br> Proceedings of LATA 2009, <em>Lecture Notes in Computer Science</em> <strong>5457</strong>, Springer 2009, pp. 638-647.<br> <a href="http://www.springerlink.com/content/x5nkq3640w6784w4/" rel="nofollow">http://www.springerlink.com/content/x5nkq3640w6784w4/</a></p> <p>For the question of aperiodic sets of shapes, we have had examples with two tiles (e.g. the Penrose tiling) for a long time, although there are still only a handful of examples with a small number of shapes (&lt;10 for example). The question of a single tile was a longstanding open question, and became known as the einstein problem (a german pun). The answer now depends on your definition of "tile". For a permissive definition (a tile is a compact set that is the closure of its interior, for example) the problem was solved by Joan Taylor, who is not a professional mathematician but decided to take on this particular problem over several years. This is a significant development, but perhaps not the final answer. The tile that she found is not connected. With respect to the setting of this question, the boundary is not a closed Jordan curve, and, for me, this means that it fails "the laser cutter test" I cannot easily make the thing! This result is the preprint given in Richard Borcherds comment:</p> <p>J E S Socolar, J M Taylor An aperiodic hexagonal tile<br> <em>Journal of Combinatorial Theory, Series A</em> <strong>118</strong> pp. 2207-2231 2011<br> <a href="http://arxiv.org/abs/1003.4279" rel="nofollow">http://arxiv.org/abs/1003.4279</a></p> <p>I wrote a little bit about the story here:<br> <a href="http://maxwelldemon.com/2010/04/01/socolar_taylor_aperiodic_tile/" rel="nofollow">http://maxwelldemon.com/2010/04/01/socolar_taylor_aperiodic_tile/</a><br> and you can also find Joan Taylor's original paper, with beautiful hand-drawn images:<br> <a href="http://www.math.uni-bielefeld.de/sfb701/files/preprints/sfb10015.pdf" rel="nofollow">http://www.math.uni-bielefeld.de/sfb701/files/preprints/sfb10015.pdf</a></p> <p>On the hyperbolic plane the first strongly aperiodic set (having no symmetries of infinite order) was discovered in 2005, by Chaim Goodman-Strauss:</p> <p>C Goodman-Strauss A strongly aperiodic set of tiles in the hyperbolic plane<br> <em>Inventiones Mathematicae</em>, *<em>159</em>, Number 1, 119-132, 2005<br> <a href="http://math.uark.edu/A_Strong_Aperiodic_Set_of_Tiles_in_the_Hyberbolic_Plane%281%29.pdf" rel="nofollow">http://math.uark.edu/A_Strong_Aperiodic_Set_of_Tiles_in_the_Hyberbolic_Plane%281%29.pdf</a></p> <p>The tiling problem took a little longer, and was only shown to be undecidable recently (in 2006-7), independently by Maurice Margenstern and Jarkko Kari, who give distinct proofs. </p> <p>M Margenstern, The Domino Problem of the Hyperbolic Plane is Undecidable<br> <em>The Bulletin of the EATCS</em> <strong>93</strong> 220--237 2007<br> <a href="http://arxiv.org/abs/0706.4161" rel="nofollow">http://arxiv.org/abs/0706.4161</a></p> <p>J Kari, On the Undecidability of the Tiling Problem<br> SOFSEM 2008: Theory and Practice of Computer Science <em>Springer Lecture Notes in Computer Science</em>, <strong>4910</strong>, 74-82 2008<br> <a href="http://www.springerlink.com/content/673165n258t18741/" rel="nofollow">http://www.springerlink.com/content/673165n258t18741/</a> </p>