The Tiling Problem

Wang tiles, first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are modelled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them. The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The algorithmic problem of determining whether a tile set can tile the plane became known as the domino (or tiling) problem. In 1966, Wang's student Robert Berger proved the domino problem is undecidable (no algorithm for the problem can exist).