The Domino problem is undecidable on every rhombus subshift

02/23/2023

∙

by   Benjamin Hellouin de Menibus, et al.

∙

0

∙

share

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.