Wang tile

Example

A Wang tile is a unit square whose four edges carry colours from a finite set. Fix a finite set $W$ of Wang tiles. A tiling by $W$ is a map $\tau \colon \Z^2 \to W$ such that adjacent edges match. That is, for each $(i, j)$, the right edge of $\tau(i, j)$ has the colour of the left edge of $\tau(i+1, j)$. Also the top edge of $\tau(i, j)$ has the colour of the bottom edge of $\tau(i, j+1)$. Tiles may not be rotated or reflected.

The set of all tilings by $W$ is a two-dimensional subshift of finite type in $W^{\Z^2}$. Indeed, its forbidden patterns are the pairs of adjacent tiles whose common edge has two different colours. There are finitely many of them.

Check of a small case: let $W$ consist of one tile whose four edges all have the colour $a$. All matching conditions hold, so the constant map is a tiling, and it is periodic. Now let $W$ consist of one tile with left edge $a$ and right edge $b \ne a$. Two such tiles can never sit side by side, so $W$ admits no tiling.