Editing Wang tile

{{Short description|Square tiles with a color on each edge}}
[[File:Wang 11 tiles.svg|thumb|This set of 11 Wang tiles will tile the plane but only [[aperiodic tiling|aperiodically]].]]
{{Commons category|Wang tiles}}

'''Wang tiles''' (or '''Wang dominoes'''), first proposed by mathematician, logician, and philosopher [[Hao Wang (academic)|Hao Wang]] in 1961, is a class of [[formal system]]s. They are modeled 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 [[tessellation|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==
[[Image:Wang tesselation.svg|thumb|400px|Example of Wang tessellation with 13 tiles.]]
In 1961, Wang conjectured that if a finite set of Wang tiles can tile the plane, then there also exists a [[tessellation|'' 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.<ref>{{citation
 | last = Wang | first = Hao | author-link = Hao Wang (academic)
 | issue = 1
 | journal = [[Bell System Technical Journal]]
 | pages = 1–41
 | title = Proving theorems by pattern recognition—II
 | volume = 40
 | year = 1961
 | doi=10.1002/j.1538-7305.1961.tb03975.x}}. Wang proposes his tiles and conjectures that there are no aperiodic sets.</ref><ref>{{citation
 | last = Wang | first = Hao | author-link = Hao Wang (academic)
 | date = November 1965
 | journal = [[Scientific American]]
 | pages = 98–106
 | title = Games, logic and computers| volume = 213 | issue = 5 | doi = 10.1038/scientificamerican1165-98 | bibcode = 1965SciAm.213e..98W }}. Presents the domino problem for a popular audience.</ref> 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.<ref>{{citation
 | last = Renz | first = Peter
 | doi = 10.2307/3027370
 | issue = 2
 | journal = The Two-Year College Mathematics Journal
 | pages = 83–103
 | title = Mathematical proof: What it is and what it ought to be
 | volume = 12
 | year = 1981| jstor = 3027370
 }}.</ref> The algorithmic problem of determining whether a tile set can tile the plane became known as the '''domino problem'''.<ref name="berger"/>

According to Wang's student, [[Robert Berger (mathematician)|Robert Berger]],<ref name="berger"/>
<blockquote>
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.
</blockquote>
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, [[Robert Berger (mathematician)|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.<ref name="berger">{{citation
 | last = Berger | first = Robert | author-link = Robert Berger (mathematician)
 | journal = Memoirs of the American Mathematical Society
 | mr = 0216954
 | page = 72
 | title = The undecidability of the domino problem
 | volume = 66
 | year = 1966}}.  Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.</ref>

==Aperiodic sets of tiles==
[[File:Wang_11_tiles_monochromatic.svg|thumb|Wang tiles made monochromatic by replacing edges of each quadrant with a shape corresponding on its colour &ndash; this set is isomorphic to Jeandel and Rao's minimal set above]]
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 ''[[aperiodic tiling|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.<ref>{{citation
 | last = Robinson | first = Raphael M. | author-link = Raphael Robinson
 | journal = [[Inventiones Mathematicae]]
 | mr = 0297572
 | pages = 177–209
 | title = Undecidability and non periodicity for tilings of the plane
 | volume = 12
 | year = 1971
 | issue = 3 | doi=10.1007/bf01418780| bibcode = 1971InMat..12..177R| s2cid = 14259496 }}.</ref><ref name="culik">{{citation
 | last = Culik | first = Karel II
 | doi = 10.1016/S0012-365X(96)00118-5
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1417576
 | pages = 245–251
 | title = An aperiodic set of 13 Wang tiles
 | volume = 160
 | year = 1996| doi-access = free
 }}. (Showed an aperiodic set of 13 tiles with 5 colors.)</ref><ref>{{citation
 | last = Kari | first = Jarkko | author-link = Jarkko Kari
 | doi = 10.1016/0012-365X(95)00120-L
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1417578
 | pages = 259–264
 | title = A small aperiodic set of Wang tiles
 | volume = 160
 | year = 1996| doi-access = free
 }}.</ref><ref name="jeandel">{{citation
 | last1 = Jeandel | first1 = Emmanuel
 | last2 = Rao | first2 = Michaël
 | arxiv = 1506.06492
 | doi = 10.19086/aic.18614
 | journal = Advances in Combinatorics
 | mr = 4210631
 | page = 1:1–1:37
 | title = An aperiodic set of 11 Wang tiles
 | year = 2021| s2cid = 13261182
 }}. (Showed an aperiodic set of 11 tiles with 4 colors, and proved that fewer tiles or fewer colors cannot be aperiodic.)</ref> For example, a set of 13 aperiodic tiles was published by Karel Culik II in 1996.<ref name="culik"/>

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.<ref name="jeandel" /> 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.<ref>{{citation
 | last1 = Culik | first1 = Karel II
 | last2 = Kari | first2 = Jarkko | author2-link = Jarkko Kari
 | issue = 10
 | journal = [[Journal of Universal Computer Science]]
 | mr = 1392428
 | pages = 675–686
 | title = An aperiodic set of Wang cubes
 | url = http://www.jucs.org/jucs_1_10/an_aperiodic_set_of
 | volume = 1
 | year = 1995 | doi=10.1007/978-3-642-80350-5_57}}.</ref> Winfree et al. have demonstrated the feasibility of creating molecular "tiles" made from [[DNA]] (deoxyribonucleic acid) that can act as Wang tiles.<ref>{{citation
 | last1 = Winfree | first1 = E.
 | last2 = Liu | first2 = F.
 | last3 = Wenzler | first3 = L.A.
 | last4 = Seeman | first4 = N.C.
 | journal = [[Nature (journal)|Nature]]
 | pages = 539–544
 | title = Design and self-assembly of two-dimensional DNA crystals
 | volume = 394
 | year = 1998
 | issue = 6693
 | doi = 10.1038/28998 | pmid=9707114| bibcode = 1998Natur.394..539W| s2cid = 4385579
 }}.</ref> Mittal et al. have shown that these tiles can also be composed of [[peptide nucleic acid]] (PNA), a stable artificial mimic of DNA.<ref>{{citation
 | last1 = Lukeman | first1 = P.
 | last2 = Seeman | first2 = N.
 | last3 = Mittal | first3 = A.
 | contribution = Hybrid PNA/DNA nanosystems
 | title = 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii
 | year = 2002}}.</ref>

==Applications==
Wang tiles have been used for [[procedural synthesis]] of [[procedural texture|textures]], [[heightfield]]s, 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.<ref>{{citation
 | last = Stam | first = Jos
 | title = Aperiodic Texture Mapping
 | url = http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/R046.pdf
 | year = 1997}}. Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.</ref><ref>{{citation
 | last1 = Neyret | first1 = Fabrice
 | last2 = Cani | first2 = Marie-Paule
 | title = Proceedings of the 26th annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '99
 | contribution = Pattern-Based Texturing Revisited
 | doi = 10.1145/311535.311561
 | location = Los Angeles, United States
 | pages = 235–242
 | publisher = ACM
 | url = https://hal.inria.fr/inria-00537511/file/patternTexture.pdf
 | year = 1999| isbn = 0-201-48560-5
 | s2cid = 11247905
 }}. Introduces stochastic tiling.</ref><ref>{{citation
 | last1 = Cohen | first1 = Michael F. |author1-link=Michael F. Cohen
 | last2 = Shade | first2 = Jonathan
 | last3 = Hiller | first3 = Stefan
 | last4 = Deussen | first4 = Oliver
 | title = ACM SIGGRAPH 2003 Papers on - SIGGRAPH '03 | contribution = Wang tiles for image and texture generation
 | doi = 10.1145/1201775.882265
 | isbn = 1-58113-709-5
 | location = New York, NY, USA
 | pages = 287–294
 | publisher = ACM
 | url = http://research.microsoft.com/~cohen/WangFinal.pdf | archive-url = https://web.archive.org/web/20060318064425/http://research.microsoft.com/~cohen/WangFinal.pdf  | archive-date = 2006-03-18 | year = 2003| s2cid = 207162102 }}. </ref><ref>{{citation
 | last = Wei | first = Li-Yi
 | contribution = Tile-based texture mapping on graphics hardware
 | doi = 10.1145/1058129.1058138
 | isbn = 3-905673-15-0
 | location = New York, NY, USA
 | pages = 55–63
 | publisher = ACM
 | title = Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04)
 | url = http://graphics.stanford.edu/papers/tile_mapping_gh2004/
 | year = 2004| s2cid = 53224612
 }}. Applies Wang Tiles for real-time texturing on a GPU.</ref><ref>. {{citation
 | last1 = Kopf | first1 = Johannes
 | last2 = Cohen-Or | first2 = Daniel
 | last3 = Deussen | first3 = Oliver
 | last4 = Lischinski | first4 = Dani
 | title = ACM SIGGRAPH 2006 Papers on - SIGGRAPH '06
 | contribution = Recursive Wang tiles for real-time blue noise
 | doi = 10.1145/1179352.1141916
 | isbn = 1-59593-364-6
 | location = New York, NY, USA
 | pages = 509–518
 | publisher = ACM
 | url = http://johanneskopf.de/publications/blue_noise
 | year = 2006| s2cid = 11007853
 }}. Shows advanced applications.</ref>

Wang tiles have also been used in [[cellular automaton|cellular automata theory]] [[decision problem|decidability]] proofs.<ref>{{citation
 | last = Kari | first = Jarkko | author-link = Jarkko Kari
 | contribution = Reversibility of 2D cellular automata is undecidable
 | doi = 10.1016/0167-2789(90)90195-U
 | issue = 1–3
 | mr = 1094882
 | pages = 379–385
 | series = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | title = Cellular automata: theory and experiment (Los Alamos, NM, 1989)
 | volume = 45
 | year = 1990| bibcode = 1990PhyD...45..379K
 }}.</ref>

==In popular culture==
The short story "[[Wang's Carpets]]", later expanded to the novel ''[[Diaspora (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.<ref>{{citation
 | last = Burnham | first = Karen
 | isbn = 978-0-252-09629-7
 | pages = 72–73
 | publisher = University of Illinois Press
 | series = Modern Masters of Science Fiction
 | title = Greg Egan
 | url = https://books.google.com/books?id=lPAwAwAAQBAJ&pg=PA72
 | year = 2014}}.</ref>

==See also==
* [[Edge-matching puzzle]]

==References==
{{reflist}}

==Further reading==
* {{citation|author1-link=Branko Grünbaum|last1=Grünbaum|first1=Branko|last2=Shephard|first2=G. C.|title=Tilings and Patterns|location=New York|publisher=W. H. Freeman|year=1987|isbn=0-7167-1193-1|url-access=registration|url=https://archive.org/details/isbn_0716711931}}.

==External links==
* [https://web.archive.org/web/20170803085704/http://www.uwgb.edu/dutchs/symmetry/aperiod.htm Steven Dutch's page including many pictures of aperiodic tilings]
* [http://catseye.tc/installation/Backtracking_Wang_Tiler Animated demonstration of a naïve Wang tiling method] - requires Javascript and HTML5

{{Tessellation}}

[[Category:1961 introductions]]
[[Category:Aperiodic tilings]]
[[Category:Euclidean tilings]]
[[Category:Theory of computation]]
[[Category:Undecidable problems]]