Answers are grounded in this paper and cite their sources.
This work reveals tiling with two prototiles is undecidable, indicating new limits in combinatorial tiling problems.
We show that the following problem is undecidable: given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them. This improves a result of Demaine and Langerman [SoCG 2025], who showed undecidability for three tiles. Along the way, we show that tiling with one prototile is undecidable if there can be edge-to-edge matching rules. This is the first result to show undecidability for monotiling with only local matching constraints.
No takes yet. Share an insight, caveat, or question.
Jack Stade (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: