The standard question is whether a given finite set can tile the plane. This means that copies of the tiles can be arranged to fill an infinite plane, such that contiguous edges always have the same color. The tiles cannot be rotated or reflected.
In 1961, Wang proposed an algorithm to take any finite set of tiles and decide whether they tiled the plane. To prove his algorithm worked, he had to make one assumption. He assumed any set that could tile the plane, would be able to tile the plane periodically (with a pattern that repeats, like standard wallpaper).
However, in 1966 Robert Berger proved Wang's conjecture was wrong. He presented a set of Wang tiles that could only tile the plane aperiodically. This meant it could fill the plane without holes, but the tiling couldn't be a simple repetition of a finite pattern. This is similar to a Penrose tiling, or the arrangement of atoms in a quasicrystal. Although Berger's original set contained 20,426 tiles, he hypothesized that smaller sets would work, including subsets of his set. In later years, increasingly smaller sets were found. For example, the set of 13 tiles given above is an aperiodic set published by Karel Culik. It can tile the plane, but not periodically.
Wang's algorithm for determining whether a set of tiles can tile the plane was not correct. In fact, no such algorithm can exist. It is possible to translate any Turing machine into a set of Wang tiles, such that the Wang tiles can tile the plane if and only if the Turing machine will never halt. The halting problem is uncomputable, therefore the Wang tiling problem is also uncomputable. In a sense, Wang tiles have computational power equivalent to that of a Turing machine.
Wang tiles can be generalized in various ways, all of which are also undecidable in the above sense. For example, Wang cubes are equal-sized cubes with colored faces. Culik and Kari have demonstrated aperiodic sets of Wang cubes. Seeman et. al. have demonstrated the feasability of creating molecular "tiles" made from DNA (deoxyribonucleic acid) that can act as Wang tiles. Mittal et. al have shown that these tiles can also be composed of PNA (peptide nucleic acid), a stable artificial mimic of DNA.
External links and references