The Domino problem is undecidable on every rhombus subshift

Abstract

We extend the classical Domino problem to any tiling of rhombus-shaped tiles. For any subshift X of edge-to-edge rhombus tilings, such as the Penrose subshift, we prove that the associated X-Domino problem is ${\Pi }_1^0$ -hard and therefore undecidable. It is ${\Pi }_1^0$ -complete when the subshift X is given by a computable sequence of forbidden patterns.

12 pages + 1 page of appendix

Cited by in corpus (1)

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