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$?



Decidability of (restricted) periodicity of Wang tilings
This is undecidable. I refer to the proof of the periodic tiling problem which is Theorem 5.7 in the lecture notes of Jarkko Kari
<https://users.utu.fi/jkari/wp-content/uploads/sites/1251/2021/10/part2.pdf>
but I give a construction that works with any such proof where the period is suitably marked.


In the proof I cite, in the periodic configurations, there are explicit horizontal and vertical fault lines, which mark the period. (I'll need only the horizontal fault lines.) More precisely, this construction has the property that the set of tiles (constructed from some Turing machine $M$) can be (algorithmically) partitioned as $T = T\_1 \sqcup T\_2$ so that


* If the machine $M$ halts, there is a periodic configuration with period $(0,m)$ such that the tiles on rows $mk$ come from $T\_1$, and others from $T\_2$.
* In every periodic configuration (should one exist), tiles from $T\_1$ are used.
* If the machine $M$ does not halt, there is no periodic configuration.


On any such construction we can perform a post-processing step where we add a constant shear to the horizontal fault lines when we see tiles $T\_1$. Wang tiles are equivalent to subshifts of finite type, so it suffices to explain how to make a subshift of finite type. We first add the constraint that each row is explicitly enforced to have only tiles from $T\_1$, or only from $T\_2$. Then we make $T\_1$ tiles check their color constraint not with their top neighbor, but their top neighbor's right$^n$ neighbor.


Now I claim the resulting subshift of finite type has an $(n,m)$-periodic configuration if and only if $M$ halts. Proof:


* If $M$ halts, take a valid Wang tiling by $T$ coming from the first item. To get it in our SFT, for each line over $T\_1$, shear the half-plane above by $n$ steps to the right (and take a limit). Because the period was $(0,m)$ initially, and $T\_1$-rows appear on every $m$th row, this gives an $(n,m)$-periodic configuration.
* Suppose our new subshift of finite type has a periodic point. If it doesn't use tiles from $T\_1$, this is a periodic Wang tiling over $T\_2$, which is forbidden by item 2 above. It tiles from $T\_1$ are used, they are used on entire rows, and the sequence of rows where they are used is periodic as well. Clearly we get a periodic configuration of the original Wang tile set by shearing by $-n$ on top of the $T\_1$-rows. So $M$ halts.


So we have reduced the halting problem of $M$ algorithmically to the existence of an $(n,m)$-periodic point in a subshift of finite type (for our fixed $n$). As mentioned we can easily convert to Wang tiles if we wish.


(One can also phrase the proof as reducing a technical variant of the periodic tiling problem "with marked periods" directly to OP's problem, and noting that the proof in the lecture notes proves this technical variant.)


