HOME

TheInfoList



OR:

Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of
formal system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A form ...
s. They are modelled 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
tile Tiles are usually thin, square or rectangular coverings manufactured from hard-wearing material such as ceramic, stone, metal, baked clay, or even glass. They are generally fixed in place in an array to cover roofs, floors, walls, edges, or o ...
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 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 Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also ca ...
, 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. According to Wang's student, Robert Berger,
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 In logic, mathematics and computer science, especially metalogic and computability theory, an effective methodGeoffrey Hunter (logician), Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University o ...
that correctly settles the problem for all given domino sets. In 1966,
Berger Berger is a surname in both German language, German and French language, French, although there is no etymological connection between the names in the two languages. The French surname is an occupational name for a shepherd, from Old French ''bergi ...
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 A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
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 In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
(the problem of testing whether a Turing machine eventually halts) then implies the undecidability of Wang's tiling problem.. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.


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 A Penrose tiling is an example of an aperiodic tiling. Here, a ''tiling'' is a covering of the plane by non-overlapping polygons or other shapes, and ''aperiodic'' means that shifting any tiling with these shapes by any finite distance, without r ...
, or the arrangement of atoms in a
quasicrystal A quasiperiodic crystal, or quasicrystal, is a structure that is ordered but not periodic. A quasicrystalline pattern can continuously fill all available space, but it lacks translational symmetry. While crystals, according to the classical cr ...
. 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.. (Showed an aperiodic set of 13 tiles with 5 colors.). (Showed an aperiodic set of 11 tiles with 4 colors, and proved that fewer tiles or fewer colors cannot be aperiodic.) 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 A tessellation or tiling is the covering of a surface, often a plane (mathematics), plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to high-dimensional ...
. 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 Peptide nucleic acid (PNA) is an artificially synthesized polymer similar to DNA or RNA. Synthetic peptide nucleic acid oligomers have been used in recent years in molecular biology procedures, diagnostic assays, and antisense therapies. Due to ...
(PNA), a stable artificial mimic of DNA.


Applications

Wang tiles have been used for
procedural synthesis In computing, procedural generation is a method of creating data algorithmically as opposed to manually, typically through a combination of human-generated assets and algorithms coupled with computer-generated randomness and processing power. In ...
of textures,
heightfield In computer graphics, a heightmap or heightfield is a raster image used mainly as Discrete Global Grid in secondary elevation modeling. Each pixel stores values, such as surface elevation data, for display in 3D computer graphics. A heightm ...
s, 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. 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 A diaspora ( ) is a population that is scattered across regions which are separate from its geographic place of origin. Historically, the word was used first in reference to the dispersion of Greeks in the Hellenic world, and later Jews after ...
'', by
Greg Egan Greg Egan (born 20 August 1961) is an Australian science fiction writer and amateur mathematician, best known for his works of hard science fiction. Egan has won multiple awards including the John W. Campbell Memorial Award, the Hugo Award, an ...
, postulates a universe, complete with resident organisms and intelligent beings, embodied as Wang tiles implemented by patterns of complex molecules..


See also

*
Edge-matching puzzle An edge-matching puzzle is a type of tiling puzzle involving tiling an area with (typically regular) polygons whose edges are distinguished with colours or patterns, in such a way that the edges of adjacent tiles match. Edge-matching puzzles are k ...


References


Further reading

* .


External links


Steven Dutch's page including many pictures of aperiodic tilings

Animated demonstration of a naïve Wang tiling method
- requires Javascript and HTML5 {{Tessellation 1961 introductions Aperiodic tilings Euclidean tilings Theory of computation Undecidable problems