Decidability of tiling R^2

2011-01-27T17:44:12Z

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?

I know the general problem of a set of polygons is undecidable, but I haven't found any information on the single tile case.

Answer by ARupinski for Decidability of tiling R^2

2011-01-27T18:02:19Z

Isn't this question equivalent to the Heesch Problem of determining how much of the plane can be tiled by a given single tile?

See http://math.uttyler.edu/cmann/math/heesch/heesch.htm for examples.

Answer by Ricky Demer for Decidability of tiling R^2

2011-01-27T18:32:38Z

Yes.

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}$)".

Then it is undecidable in ZFC whether C can tile the plane.

EDIT:
Now, perhaps you could say what you do mean by "constructable in the same axiomatic system which it is undecidable", since I am completely stumped.

Answer by Nick S for Decidability of tiling R^2

2011-01-27T23:00:09Z

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.

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.

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.

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...

Answer by Edmund Harriss for Decidability of tiling R^2

2011-09-22T01:11:28Z

The answer by Nick S is essentially correct, but I can provide a little more detail.

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.

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.

R Berger The undecidability of the domino problem
Mem. Amer. Math. Soc. 66 1966
http://books.google.com/books/about/Undecidability_of_the_Domino_Problem.html?id=8AmiHD0Lbu8C

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.

R M Robinson, Undecidability and Nonperiodicity for Tilings of the Plane
Inventiones math. 12 177-209, 1971
http://www.lif.univ-mrs.fr/~fernique/qc/robinson.pdf

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.

N Ollinger, Tiling the Plane with a Fixed Number of Polyominoes.
Proceedings of LATA 2009, Lecture Notes in Computer Science 5457, Springer 2009, pp. 638-647.
http://www.springerlink.com/content/x5nkq3640w6784w4/

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 (<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:

J E S Socolar, J M Taylor An aperiodic hexagonal tile
Journal of Combinatorial Theory, Series A 118 pp. 2207-2231 2011
http://arxiv.org/abs/1003.4279

I wrote a little bit about the story here:
http://maxwelldemon.com/2010/04/01/socolar_taylor_aperiodic_tile/
and you can also find Joan Taylor's original paper, with beautiful hand-drawn images:
http://www.math.uni-bielefeld.de/sfb701/files/preprints/sfb10015.pdf

On the hyperbolic plane the first strongly aperiodic set (having no symmetries of infinite order) was discovered in 2005, by Chaim Goodman-Strauss:

C Goodman-Strauss A strongly aperiodic set of tiles in the hyperbolic plane
Inventiones Mathematicae, *159, Number 1, 119-132, 2005
http://math.uark.edu/A_Strong_Aperiodic_Set_of_Tiles_in_the_Hyberbolic_Plane%281%29.pdf

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.

M Margenstern, The Domino Problem of the Hyperbolic Plane is Undecidable
The Bulletin of the EATCS 93 220--237 2007
http://arxiv.org/abs/0706.4161

J Kari, On the Undecidability of the Tiling Problem
SOFSEM 2008: Theory and Practice of Computer Science Springer Lecture Notes in Computer Science, 4910, 74-82 2008
http://www.springerlink.com/content/673165n258t18741/

Decidability of tiling R^2 - MathOverflow

Decidability of tiling R^2

Answer by ARupinski for Decidability of tiling R^2

Answer by Ricky Demer for Decidability of tiling R^2

Answer by Nick S for Decidability of tiling R^2

Answer by Edmund Harriss for Decidability of tiling R^2