The Domino problem is undecidable on every rhombus subshift
| Autor: | de Menibus, Benjamin Hellouin, Lutfalla, Victor H., Noûs, Camille |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/978-3-031-33264-7_9 |
| Popis: | 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^0_1$ -hard and therefore undecidable. It is $\Pi^0_1$ -complete when the subshift X is given by a computable sequence of forbidden patterns. Comment: 12 pages + 1 page of appendix |
| Databáze: | arXiv |
| Externí odkaz: |
|