Wang tile

In 1961, Wang conjectured that if a finite set of Wang tiles can tile the plane, then there also exists a periodic tiling, which, mathematically, is a tiling that is invariant under translations by vectors in a 2-dimensional lattice. This can be likened to the periodic tiling in a wallpaper pattern, where the overall pattern is a repetition of some smaller pattern. He also observed that this conjecture would imply the existence of an algorithm to decide whether a given finite set of Wang tiles can tile the plane. The idea of constraining adjacent tiles to match each other occurs in the game of dominoes, so Wang tiles are also known as Wang dominoes. The algorithmic problem of determining whether a tile set can tile the plane became known as the domino problem. ==Aperiodic sets of tiles==

Combining Berger's undecidability result with Wang's observation shows that there must exist a finite set of Wang tiles that tiles the plane, but only aperiodically. 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 conjectured that smaller sets would work, including subsets of his set, and in his unpublished Ph.D. thesis, he reduced the number of tiles to 104. In later years, ever smaller sets were found. For example, a set of 13 aperiodic tiles was published by Karel Culik II in 1996. The smallest set of aperiodic tiles was discovered by Emmanuel Jeandel and Michael Rao in 2015, with 11 tiles and 4 colors. They used an exhaustive computer search to prove that 10 tiles or 3 colors are insufficient to force aperiodicity. This set, shown above in the title image, can be examined more closely at :File: Wang 11 tiles.svg. ==Generalizations==

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, and side colors can be matched on any polygonal tessellation. Culik and Kari have demonstrated aperiodic sets of Wang cubes. Winfree et al. have demonstrated the feasibility 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 peptide nucleic acid (PNA), a stable artificial mimic of DNA. ==Applications==

Wang tiles have been used for procedural synthesis of textures, heightfields, and other large and nonrepeating bi-dimensional data sets; a small set of precomputed or hand-made source tiles can be assembled very cheaply without too obvious repetitions and periodicity. In this case, traditional aperiodic tilings would show their very regular structure; much less constrained sets that guarantee at least two tile choices for any two given side colors are common because tileability is easily ensured and each tile can be selected pseudorandomly. Wang tiles have also been used in cellular automata theory decidability proofs. ==In popular culture==

The short story "Wang's Carpets", later expanded to the novel Diaspora, by Greg Egan, postulates a universe, complete with resident organisms and intelligent beings, embodied as Wang tiles implemented by patterns of complex molecules. ==See also==