Undecidability of Translational Tiling of the Plane with Four Tiles
By: Chao Yang, Zhujun Zhang
Potential Business Impact:
Makes it impossible to know if shapes fit together.
The translational tiling problem, dated back to Wang's domino problem in the 1960s, is one of the most representative undecidable problems in the field of discrete geometry and combinatorics. Ollinger initiated the study of the undecidability of translational tiling with a fixed number of tiles in 2009, and proved that translational tiling of the plane with a set of $11$ polyominoes is undecidable. The number of polyominoes needed to obtain undecidability was reduced from $11$ to $7$ by Yang and Zhang, and then to $5$ by Kim. We show that translational tiling of the plane with a set of $4$ (disconnected) polyominoes is undecidable in this paper.
Similar Papers
Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
Combinatorics
Makes computers unable to solve some shape-fitting puzzles.
On the Undecidability of Tiling the $3$-dimensional Space with a Set of $3$ Polycubes
Combinatorics
Makes it impossible to know if shapes fill space.
Two Tiling is Undecidable
Computational Geometry
Can't tell if shapes tile the whole floor.