8
votes
3answers
299 views

Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation: coloring in lattice Reference for Wang Tile Computational approach deciding whether a set of Wang Tile could tile the space up to some size ...
4
votes
1answer
182 views

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
2
votes
0answers
156 views

Are there any recommended texts that cover Turing Tilings?

I have read the original paper by Wang, as well as a paper by Boas [1996] entitled 'the Convenience of Tilings', but wanted to know if there were any other texts that people could recommend that ...
13
votes
4answers
994 views

Decidability of tiling R^2

Does there exist a closed curve, with finite area and finite circumference, of which it is undecidable (in an axiomatic system where it is constructable) whether it can tile the plane? I know the ...