Skip to main content
MathOverflow

Return to Question

fixed typo
Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Possible weaker version of the Domino\WangDomino/Wang tiling problem

This may be a dumb question, but I was wondering whether the question of 'periodically tiling the plane from a finite set of tiles' is the same as the domino tiling problem or a weaker version. I think the difference of my question to the domino problem, is whether assuming you don't have to use all the tiles helps solve the problem?

As was answered here and is also widely known, the domino problem is undecideableundecidable. I am unsure if my question is covered by the general domino tiling problem, or is perhaps a decidable variant?

I am specifically interested in given a finite collection of colors $ \mathcal{A} $ and prohibiting a set of $\mathcal{A}$-colored $2\times 2$ patches, can one determine whether a periodic coloring of $\mathbb{Z}^2$ under these conditions is possible?

Possible weaker version of the Domino\Wang tiling problem

This may be a dumb question, but I was wondering whether the question of 'periodically tiling the plane from a finite set of tiles' is the same as the domino tiling problem or a weaker version. I think the difference of my question to the domino problem, is whether assuming you don't have to use all the tiles helps solve the problem?

As was answered here and is also widely known, the domino problem is undecideable. I am unsure if my question is covered by the general domino tiling problem, or is perhaps a decidable variant?

I am specifically interested in given a finite collection of colors $ \mathcal{A} $ and prohibiting a set of $\mathcal{A}$-colored $2\times 2$ patches, can one determine whether a periodic coloring of $\mathbb{Z}^2$ under these conditions is possible?

Possible weaker version of the Domino/Wang tiling problem

This may be a dumb question, but I was wondering whether the question of 'periodically tiling the plane from a finite set of tiles' is the same as the domino tiling problem or a weaker version. I think the difference of my question to the domino problem, is whether assuming you don't have to use all the tiles helps solve the problem?

As was answered here and is also widely known, the domino problem is undecidable. I am unsure if my question is covered by the general domino tiling problem, or is perhaps a decidable variant?

I am specifically interested in given a finite collection of colors $ \mathcal{A} $ and prohibiting a set of $\mathcal{A}$-colored $2\times 2$ patches, can one determine whether a periodic coloring of $\mathbb{Z}^2$ under these conditions is possible?

Source Link
Keen-ameteur
Keen-ameteur
  • 633
  • 3
  • 9

Possible weaker version of the Domino\Wang tiling problem

This may be a dumb question, but I was wondering whether the question of 'periodically tiling the plane from a finite set of tiles' is the same as the domino tiling problem or a weaker version. I think the difference of my question to the domino problem, is whether assuming you don't have to use all the tiles helps solve the problem?

As was answered here and is also widely known, the domino problem is undecideable. I am unsure if my question is covered by the general domino tiling problem, or is perhaps a decidable variant?

I am specifically interested in given a finite collection of colors $ \mathcal{A} $ and prohibiting a set of $\mathcal{A}$-colored $2\times 2$ patches, can one determine whether a periodic coloring of $\mathbb{Z}^2$ under these conditions is possible?