I'm reading about Wang's tessellation problem and the text mentions a simpler version: If we consider a finite set of tiles $W_{n}=\{w_{1},...,w_{n}\}$ where $n$ is bounded then the claim is that now the problem is in $R$.

Of course, after writing this claim the text adds the comment $$ \text{(Why ? )} $$

which left me thinking about it.

I fail to see how $n$ being bounded helps, since $\mathbb{R}^{2}$ is still infinite and so this doesn't seem like a finite problem to me. Moreover, given some specific $n$ (not bounded a priory) it seems that we could of solved the 'easy' problem with that $n$ thinking of it as a constant (/bounded).

Can someone help me understand the reasoning ?

  • $\begingroup$ If you're referring to the "standard" tiling problem ("Given a set of Wang tiles, do they tessellate the plane?") and the set of tiles can be picked only from a finite set $W_n$ you get a finite problem (trivially decidable because there are only $2^n$ instances and can be solved with a lookup table .... even though for a particular $W_n$ we will probably never know such a table :-). $\endgroup$ – Marzio De Biasi Aug 7 '15 at 17:59

Your Answer

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

Browse other questions tagged or ask your own question.