Wang tile

This set of 13 Wang tiles will tile the plane but only aperiodically.
Example of Wang tessellation with 13 tiles.
Wikimedia Commons has media related to Wang tiles.

Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected (for example the set in the picture). Then copies of the tiles are arranged side by side with matching colors, but without rotating or reflecting the tiles.

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 next question is whether this can be done in a periodic pattern.

Domino problem

In 1961, Wang conjectured that if a finite set of Wang tiles can tile the plane, then there exists also a periodic tiling, i.e., a tiling that is invariant under translations by vectors in a 2-dimensional lattice, like a wallpaper 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.[1][2] 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.[3] The algorithmic problem of determining whether a tile set can tile the plane became known as the domino problem.[4]

According to Wang's student, Robert Berger,[4]

The Domino Problem deals with the class of all domino sets. It consists of deciding, for each domino set, whether or not it is solvable. We say that the Domino Problem is decidable or undecidable according to whether there exists or does not exist an algorithm which, given the specifications of an arbitrary domino set, will decide whether or not the set is solvable.

In other words, the domino problem asks whether there is an effective procedure that correctly settles the problem for all given domino sets.

In 1966, Wang's student Robert Berger solved the domino problem in the negative. He proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem (the problem of testing whether a Turing machine eventually halts) then implies the undecidability of Wang's tiling problem.[4]

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, increasingly smaller sets were found.[5][6][7] [8] For example, the set of 13 tiles given in the image above is an aperiodic set published by Karel Culik II in 1996.[6] It can tile the plane, but not periodically. A smaller set of 11 tiles using 4 colors was discovered by Emmanuel Jeandel and Michael Rao in 2015, using an exhaustive search to prove that 10 tiles and/or 3 colors were insufficient to force aperiodicity.[8]

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.[9] Winfree et al. have demonstrated the feasibility of creating molecular "tiles" made from DNA (deoxyribonucleic acid) that can act as Wang tiles.[10] Mittal et al. have shown that these tiles can also be composed of peptide nucleic acid (PNA), a stable artificial mimic of DNA.[11]

Applications

Wang tiles have recently become a popular tool for procedural synthesis of textures, heightfields, and other large and nonrepeating bidimensional data sets; a small set of precomputed or hand-made source tiles can be assembled very cheaply without too obvious repetitions and without 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.[12][13][14][15]

Wang tiles have also been used in cellular automata theory decidability proofs.[16]

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.[17]

See also

References

  1. ↑ Wang, Hao (1961), "Proving theorems by pattern recognition—II", Bell System Technical Journal 40 (1): 1–41, doi:10.1002/j.1538-7305.1961.tb03975.x. Wang proposes his tiles, and conjectures that there are no aperiodic sets.
  2. ↑ Wang, Hao (November 1965), "Games, logic and computers", Scientific American: 98–106. Presents the domino problem for a popular audience.
  3. ↑ Renz, Peter (1981), "Mathematical proof: What it is and what it ought to be", The Two-Year College Mathematics Journal 12 (2): 83–103, doi:10.2307/3027370.
  4. 1 2 3 Berger, Robert (1966), "The undecidability of the domino problem", Memoirs of the American Mathematical Society 66: 72, MR 0216954. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.
  5. ↑ Robinson, Raphael M. (1971), "Undecidability and nonperiodicity for tilings of the plane", Inventiones Mathematicae 12: 177–209, doi:10.1007/bf01418780, MR 0297572.
  6. 1 2 Culik, Karel, II (1996), "An aperiodic set of 13 Wang tiles", Discrete Mathematics 160 (1-3): 245–251, doi:10.1016/S0012-365X(96)00118-5, MR 1417576. (Showed an aperiodic set of 13 tiles with 5 colors).
  7. ↑ Kari, Jarkko (1996), "A small aperiodic set of Wang tiles", Discrete Mathematics 160 (1-3): 259–264, doi:10.1016/0012-365X(95)00120-L, MR 1417578.
  8. 1 2 Jeandel, Emmanuel; Rao, Michael (2015), "An aperiodic set of 11 Wang tiles", CoRR. (Showed an aperiodic set of 11 tiles with 4 colors)}
  9. ↑ Culik, Karel, II; Kari, Jarkko (1995), "An aperiodic set of Wang cubes", Journal of Universal Computer Science 1 (10): 675–686, doi:10.1007/978-3-642-80350-5_57, MR 1392428.
  10. ↑ Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C. (1998), "Design and self-assembly of two-dimensional DNA crystals", Nature 394: 539–544, doi:10.1038/28998, PMID 9707114.
  11. ↑ Lukeman, P.; Seeman, N.; Mittal, A. (2002), "Hybrid PNA/DNA nanosystems", 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii.
  12. ↑ Stam, Jos (1997), Aperiodic Texture Mapping (PDF). Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
  13. ↑ Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), "Wang tiles for image and texture generation", ACM SIGGRAPH 2003 (PDF), New York, NY, USA: ACM, pp. 287–294, doi:10.1145/1201775.882265, ISBN 1-58113-709-5. Introduces stochastic tiling.
  14. ↑ Wei, Li-Yi (2004), "Tile-based texture mapping on graphics hardware", Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM, pp. 55–63, doi:10.1145/1058129.1058138, ISBN 3-905673-15-0. Applies Wang Tiles for real-time texturing on a GPU.
  15. ↑ . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006), "Recursive Wang tiles for real-time blue noise", ACM SIGGRAPH 2006, New York, NY, USA: ACM, pp. 509–518, doi:10.1145/1179352.1141916, ISBN 1-59593-364-6. Shows advanced applications.
  16. ↑ Kari, Jarkko (1990), "Reversibility of 2D cellular automata is undecidable", Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena 45 (1-3), pp. 379–385, doi:10.1016/0167-2789(90)90195-U, MR 1094882.
  17. ↑ Burnham, Karen (2014), Greg Egan, Modern Masters of Science Fiction, University of Illinois Press, pp. 72–73, ISBN 9780252096297.

Further reading

External links

This article is issued from Wikipedia - version of the Thursday, May 05, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.