A proof is claimed that determining whether a set of five polyominoes can tile the plane is undecidable, via a new edge-labeling construction.
Tiling with Three Polygons is Undecidable
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We prove that the following problem is co-RE-complete and thus undecidable: given three simple polygons, is there a tiling of the plane where every tile is an isometry of one of the three polygons (either allowing or forbidding reflections)? This result improves on the best previous construction which requires five polygons.
fields
math.CO 1years
2025 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Undecidability of Tiling the Plane with a Set of 5 Polyominoes
A proof is claimed that determining whether a set of five polyominoes can tile the plane is undecidable, via a new edge-labeling construction.