The Domino problem is undecidable on every rhombus subshift

Benjamin Hellouin de Menibus (1) , Victor H Lutfalla (2) , Camille Noûs (3)

1 LISN - Laboratoire Interdisciplinaire des Sciences du Numérique
2 Equipe AMACC - Laboratoire GREYC - UMR6072
3 Laboratoire Cogitamus

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 Π 0 1-hard and therefore undecidable. It is Π 0 1-complete when the subshift X is given by a computable sequence of forbidden patterns.

Keywords: Rhombus tiling; Decidability; Domino problem

Domains: Computer Science [cs]; Mathematics [math]

Benjamin Hellouin de Menibus, Victor H Lutfalla, Camille Noûs. The Domino problem is undecidable on every rhombus subshift. 2023. ⟨hal-04004801⟩