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 determineif a single given tile can tile the plane, a monohedral tiling.If this remains unsettled, I would be interested to know what is the minimumcardinality of a set of tiles for which there is an undecidability proof.(I have not yet accessed Berger's proof.)
Is it decidable to determine if a given shape can tile the plane?
reference request;co.combinatorics;decidability;undecidability
According to the introduction of [1],The complexity of determining if a single polyomino tiles the plane remains open [2,3], andThere 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 AmericanMathematical Society, 57(3):343356, 2010.[4] N. Ollinger. Tiling the plane with a fixed number of polyominoes. InA. H. Dediu, A. M. Ionescu, and C. Martn-Vide, editors, LATA 2009,volume 5457 of LNCS, pages 638647. Springer, 2009.