Editing Wang tile (section)

==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>