5
$\begingroup$

I am seeking a reference/citation for the undecidability of the following (or a similar) tiling problem. While proving its undecidability seems to be an (under)graduate student exercise, I would like to avoid writing a detailed proof (if possible).

Let $\mathrm{T}$ be a finite set of tiles, $\mathrm{H} \subseteq \mathrm{T} \times \mathrm{T}$ be the horizontal matching relation, $\mathrm{V} \subseteq \mathrm{T} \times \mathrm{T}$ be the vertical matching relation, and let $\Box, \blacksquare \in \mathrm{T}$ be different distinguished tiles (called the final tile and the initial tile, respectively). By an $\mathrm{N}$-octant (or an $\mathrm{N}$-triangle) $\mathbb{O}$ we mean the set $\{ (n,m) \in \mathbb{N}^2 \mid m \leq n \leq \mathrm{N} \}$. A tiling of an $\mathrm{N}$-octant $\mathbb{O}$ is any function $\xi\colon \mathbb{O} \to \mathrm{T}$ such that:

  1. for all $n < \mathrm{N}$ and $(n,m) \in \mathbb{O}$ we have $(\xi(n,m), \xi(n{+}1,m)) \in \mathrm{H}$,
  2. for all $m < \mathrm{N}$ and $(n,m) \in \mathbb{O}$ we have $(\xi(n,m), \xi(n,m{+}1)) \in \mathrm{V}$,
  3. $\xi(0,0) = \blacksquare$, and
  4. $\xi(\mathrm{N},\mathrm{N}) = \Box$.

In the finite octant tiling problem we ask, given an input $(\mathrm{T}, \mathrm{H}, \mathrm{V}, \Box, \blacksquare)$, whether there exists a tiling of $\mathrm{N}$-octant for some positive $\mathrm{N}$.

Improve this question
$\endgroup$
8
  • $\begingroup$ What you call octant should be called a quadrangle. Octants are 3-dimensional objects. $\endgroup$
    – domotorp
    Commented Oct 15 at 18:54
  • 1
    $\begingroup$ Also, I don't think that you need to write any proof, as this is clearly equivalent to the Halting problem with the standard Domino tiling reduction. $\endgroup$
    – domotorp
    Commented Oct 15 at 18:58
  • 3
    $\begingroup$ Of course, these problems are equivalent. I simply do not like the attitude of leaving the details to the reader (so I either should write a proof or provide an appropriate citation). PS: I used the word "octant" because Montanari et al. used it in the context of undecidability results for certain Halpern–Shoham logics (they have an infinite version though). $\endgroup$
    – Bartosz Bednarczyk
    Commented Oct 15 at 19:09
  • 1
    $\begingroup$ Hi, I have this paper arxiv.org/abs/1505.00326 where we attribute the claim to sciencedirect.com/science/article/pii/S0890540109000637 which uses the claim but just says it's well-known; and arxiv.org/abs/2202.08555 but there we attribute it to the book "The Classical Decision Problem" by Egon Börger, Erich Grädel, Yuri Gurevich (1997). There is an Appendix A in this book specifically about the undecidability of domino problems, which gives references. So it may be that one of these can be cited. (I didn't check if it matches your definition exactly.) $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented Oct 19 at 8:10
  • 1
    $\begingroup$ @domotorp, by the way, I think that the name "octant" used here is due to the instrument, not a geometric object: en.wikipedia.org/wiki/Octant_%28instrument%29 $\endgroup$
    – Bartosz Bednarczyk
    Commented Oct 25 at 5:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.