reference-request co.combinatorics decidability undecidability: Updated Thu, 09 Jun 2022 00:24:14 GMT

Is it decidable to determine if a given shape can tile the plane?

I know that it is undecidable to determine if a set of tiles can tile the plane, a result of Berger using Wang tiles. My question is whether it is also known to be undecidable to determine if a single given tile can tile the plane, a monohedral tiling.

If this remains unsettled, I would be interested to know what is the minimum cardinality of a set of tiles for which there is an undecidability proof. (I have not yet accessed Berger's proof.)

Solution

According to the introduction of [1],

The complexity of determining if a single polyomino tiles the plane remains open [2,3], and
There is an undecidability proof for sets of 5 polyominoes [4].

[1] Stefan Langerman, Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG]

[2] C. Goodman-Strauss. Open questions in tiling. Online, published 2000.

[3] C. Goodman-Strauss. Cant decide? undecide! Notices of the American Mathematical Society, 57(3):343356, 2010.

[4] N. Ollinger. Tiling the plane with a fixed number of polyominoes. In A. H. Dediu, A. M. Ionescu, and C. Martn-Vide, editors, LATA 2009, volume 5457 of LNCS, pages 638647. Springer, 2009.

External Links

External links referenced by this document:

References

https://cstheory.stackexchange.com/questions/32538