Undecidability of tiling the plane with a fixed number of Wang bars

Abstract

To study the fixed parameter undecidability of tiling problem for a set of Wang tiles, Jeandel and Rolin show that the tiling problem for a set of 44 Wang bars is undecidable. In this paper, we improve their result by proving that whether a set of 29 Wang bars can tile the plane is undecidable. As a consequence, the tiling problem for a set of Wang tiles with color deficiency of 25 is also undecidable.

References in corpus (5)

• About the domino problem in the hyperbolic plane, a new solution: complement
• An aperiodic set of 11 Wang tiles
• Fixed Parameter Undecidability for Wang Tilesets
• A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
• The Domino problem is undecidable on every rhombus subshift