A Wang tile is a unit square with a color assigned to each of its four sides. Copies of the tiles cover the plane by translations, without rotations or reflections, and the colors on the touching sides of adjacent tiles must agree. A finite set of tile types can admit no tiling, a periodic tiling, or tilings that are necessarily aperiodic.
An aperiodic set of Wang tiles admits a tiling of the plane but no periodic tiling. Wang's conjecture asserted that such a set could not exist. Jeandel and Rao (2021) constructed an aperiodic set of 11 Wang tiles using four colors and proved that neither fewer tiles nor fewer colors suffice.
Wang tiles also encode computation. The problem of deciding whether a finite set of Wang tiles can tile the plane is recursively undecidable. Almeida and Knudstorp (2026) use this problem and its periodic variant to obtain reported undecidability results for Skvortsov logic and Medvedev logic, respectively.
