<p>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).</p>
<blockquote>
<p>Let <span class="math-container">$\mathrm{T}$</span> be a finite set of <em>tiles</em>, <span class="math-container">$\mathrm{H} \subseteq \mathrm{T} \times \mathrm{T}$</span> be the horizontal <em>matching relation</em>, <span class="math-container">$\mathrm{V} \subseteq \mathrm{T} \times \mathrm{T}$</span> be the vertical <em>matching relation</em>, and let <span class="math-container">$\Box, \blacksquare \in \mathrm{T}$</span> be different distinguished tiles (called the <em>final tile</em> and the <em>initial tile</em>, respectively).
By an <span class="math-container">$\mathrm{N}$</span>-<em>octant</em> (or an <span class="math-container">$\mathrm{N}$</span>-<em>triangle</em>) <span class="math-container">$\mathbb{O}$</span> we mean the set <span class="math-container">$\{ (n,m) \in \mathbb{N}^2 \mid m \leq n \leq \mathrm{N} \}$</span>. A <em>tiling</em> of an <span class="math-container">$\mathrm{N}$</span>-octant <span class="math-container">$\mathbb{O}$</span> is any function <span class="math-container">$\xi\colon \mathbb{O} \to \mathrm{T}$</span> such that:</p>
<ol>
<li>for all <span class="math-container">$n &lt; \mathrm{N}$</span> and <span class="math-container">$(n,m) \in \mathbb{O}$</span> we have <span class="math-container">$(\xi(n,m), \xi(n{+}1,m)) \in \mathrm{H}$</span>,</li>
<li>for all <span class="math-container">$m &lt; \mathrm{N}$</span> and <span class="math-container">$(n,m) \in \mathbb{O}$</span> we have <span class="math-container">$(\xi(n,m), \xi(n,m{+}1)) \in \mathrm{V}$</span>,</li>
<li><span class="math-container">$\xi(0,0) = \blacksquare$</span>, and</li>
<li><span class="math-container">$\xi(\mathrm{N},\mathrm{N}) = \Box$</span>.</li>
</ol>
<p>In the <em>finite octant tiling problem</em> we ask, given an input <span class="math-container">$(\mathrm{T}, \mathrm{H}, \mathrm{V}, \Box, \blacksquare)$</span>, whether there exists a tiling of <span class="math-container">$\mathrm{N}$</span>-octant for some positive <span class="math-container">$\mathrm{N}$</span>.</p>
</blockquote>

CC BY-SA 4.0
2024-10-15T18:54:50.720Z
What you call *octant* should be called a quadrangle. Octants are 3-dimensional objects.
domotorp
CC BY-SA 4.0
2024-10-15T18:58:53.653Z
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.
domotorp
CC BY-SA 4.0
2024-10-15T19:09:36.340Z
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).
Bartosz Bednarczyk
CC BY-SA 4.0
2024-10-17T20:24:24.243Z
@BartoszBednarczyk: I have used this without proof and seen it used without proofs in many papers. I agree it'd be nice indeed to have a citable reference that spells out how it works.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-10-18T07:29:47.137Z
@a3nm So it seems that I would need to write a proof and upload it, say, to ArXiV. If you remember some of the papers, could you please send me the references via email? So that I can cite them in my note.
Bartosz Bednarczyk
CC BY-SA 4.0
2024-10-19T08:10:59.753Z
Hi, I have this paper https://arxiv.org/abs/1505.00326 where we attribute the claim to https://www.sciencedirect.com/science/article/pii/S0890540109000637 which uses the claim but just says it's well-known; and https://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.)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-10-21T05:04:32.460Z
Well, none of the cited papers contains what I actually want :) So it really make sense to spend these few hours and provide a proof.
Bartosz Bednarczyk
CC BY-SA 4.0
2024-10-25T05:07:22.997Z
@domotorp, by the way, I think that the name "octant" used here is due to the instrument, not a geometric object: https://en.wikipedia.org/wiki/Octant_%28instrument%29
Bartosz Bednarczyk
<reference-request><computability><undecidability><tilings>
Reference request: Undecidability of tiling problem of finite octant
Bartosz Bednarczyk
# Reference request: Undecidability of tiling problem of finite octant

(Asked by: username_0 on 2024-10-14)

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}$.

**Tags:** reference-request, computability, undecidability, tilings

> **Comments:**
> **username_1**: What you call *octant* should be called a quadrangle. Octants are 3-dimensional objects.  
> **username_1**: 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.  
> **username_0**: 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).  
> **username_2**: @BartoszBednarczyk: I have used this without proof and seen it used without proofs in many papers. I agree it'd be nice indeed to have a citable reference that spells out how it works.  
> **username_0**: @a3nm So it seems that I would need to write a proof and upload it, say, to ArXiV. If you remember some of the papers, could you please send me the references via email? So that I can cite them in my note.  
> **username_2**: Hi, I have this paper https://arxiv.org/abs/1505.00326 where we attribute the claim to https://www.sciencedirect.com/science/article/pii/S0890540109000637 which uses the claim but just says it's well-known; and https://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.)  
> **username_0**: Well, none of the cited papers contains what I actually want :) So it really make sense to spend these few hours and provide a proof.  
> **username_0**: @username_1, by the way, I think that the name "octant" used here is due to the instrument, not a geometric object: https://en.wikipedia.org/wiki/Octant_%28instrument%29  

---

## 0 answers

