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

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

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 referenced by this document: