October 8, 2025Open Access

Two Tiling is Undecidable

Key Points

Tiling with two polygonal prototiles is proven undecidable, marking significant progress in combinatorial tiling theory.
This case enhances previous work by demonstrating that one prototile can also lead to undecidability with edge-to-edge matching rules.
The research shows that monotiling is undecidable under local matching constraints, expanding on the understanding of tile arrangements.
These findings set new challenges for combinatorial problems in theoretical computer science and discrete geometry.

Abstract

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.

Read Full Paperexternally

Bookmark

View Full Paper

Cite This Study

Jack Stade (Fri,) studied this question.

synapsesocial.com/papers/68e5c1c76950a706b22b5e20 https://doi.org/https://doi.org/10.48550/arxiv.2506.11628

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Bookmark

View Full Paper