REVIEW 3 cited by
Tiling with Three Polygons is Undecidable
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 3 Pith papers
-
Two Tiling is Undecidable
Tiling the plane with two polygonal prototiles is undecidable, improving the known three-tile bound, and monotiling under local edge-to-edge matching rules is undecidable for the first time.
-
Undecidability of Translational Tiling with Three Tiles
Deciding translational tiling of Z^4 by three connected polyhypercubes is undecidable, shown by reduction from Wang's domino problem.
-
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.
Discussion (0). Continue with ORCID to comment.