All Questions
Tagged with tiling computability-theory
8 questions
17
votes
1
answer
580
views
Aperiodic monotile in $\mathbb{R}$
Motivation. Recently a group of researchers found an aperiodic monotile in $\mathbb{R}^2$, answering a long-standing question. There are many results in higher dimensions, so let's explore the lower ...
- 48.8k
4
votes
0
answers
164
views
Tileability and computabilty
Let $n>2$ be an integer. We consider $n$ pairs $(x_1,y_1),\dotsc,(x_n,y_n)$ in $\mathbb{N}^2$, and the polygon defined by drawing a straight line from $(x_k, y_k)$ to $(x_{k+1},y_{k+1})$ and from $(...
- 48.8k
13
votes
3
answers
1k
views
(non-)existence of the aperiodic monotile
The aperiodic monotile problem asks whether there exists a single tile that every tiling of the plane made with it results non-periodic. What is known about this problem? If this tile exists, how can ...
- 561
-2
votes
1
answer
147
views
What are the formula of representation of quasicrystals and the law or mechanism of the formation [closed]
I vaguely recall that formula of representation of quasicrystals is relevant to tiling plane,and tiling plane without period is relevant to recursiveness, and do not know the mechanism or physics ...
- 3,084
5
votes
1
answer
213
views
Aperiodic set of corner Wang Tile [closed]
There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...
- 867
9
votes
3
answers
846
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
...
user46976
5
votes
1
answer
405
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 ...
- 867
10
votes
2
answers
1k
views
Decidability of periodic tilings of the plane
I'm interested in tilings of the plane by squares, with labels on the edges. It's well known that (1) the question "can one tile the plane with the following finite set of tiles?" is undecidable, and (...
- 2,519