5
$\begingroup$

Consider a Wang tiling (given a subset of $C^4$ for a finite set $C$ of colours, e.g.). It's well-known to be undecidable whether there exists a tiling, and also whether there exists a periodic tiling. It's also well-known that there exists a periodic tiling iff there exists a doubly periodic tiling.

On the other hand, for any given n, then it's decidable whether there exists a periodic tiling with period $(n,0)$: construct a directed graph with vertex set $C^n$ and an edge from $v$ to $w$ if there exists a tiling of the $n\times1$ rectangle with identical left and right labels and $v,w$ at the bottom and top respectively. Then there exists such a periodic tiling iff this graph has a loop.

Here is a question I can't answer: for any given $n$, is it decidable whether there exists a periodic tiling with period $(n,m)$ for some $m$?

$\endgroup$
  • $\begingroup$ In the last paragraph, I mean that the tiling is invariant under translation by the vector $(n,m)$ for some unknown $m$ -- see the remark below. $\endgroup$ – grok Aug 26 '16 at 21:00
2
$\begingroup$

For $m$ fixed, you can consider all proper tilings of a $1 \times m$-rows. The number of such rows is crudely bounded above by $C^{2m}$. Then, we pretend each such row is an individual Wang tile, and have thus reduced it to the $n \times 1$ case.

$\endgroup$
  • $\begingroup$ Sorry, I was unclear. By "periodic with period $(m,n)$, I meant that the tiling is invariant under translation by $(m,n)$ for some unknown $m$. $\endgroup$ – grok Aug 26 '16 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.