Wang tile

Last updated
This set of 11 Wang tiles will tile the plane but only aperiodically. Wang 11 tiles.svg
This set of 11 Wang tiles will tile the plane but only aperiodically.

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, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them.

Contents

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

Example of Wang tessellation with 13 tiles. Wang tesselation.svg
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 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. [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, 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

Wang tiles made monochromatic by replacing edges of each quadrant with a shape corresponding on its colour - this set is isomorphic to Jeandel and Rao's minimal set above Wang 11 tiles monochromatic.svg
Wang tiles made monochromatic by replacing edges of each quadrant with a shape corresponding on its colour 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 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. [5] [6] [7] [8] For example, a set of 13 aperiodic tiles was published by Karel Culik II in 1996. [6]

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. [8] 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. [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 been used 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] [16]

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

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

See also

Related Research Articles

<span class="mw-page-title-main">Conjecture</span> Proposition in mathematics that is unproven

In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's Last Theorem, have shaped much of mathematical history as new areas of mathematics are developed in order to prove them.

<span class="mw-page-title-main">Polyomino</span> Geometric shapes formed from squares

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.

<span class="mw-page-title-main">Kite (geometry)</span> Quadrilateral symmetric across a diagonal

In Euclidean geometry, a kite is a quadrilateral with reflection symmetry across a diagonal. Because of this symmetry, a kite has two equal angles and two pairs of adjacent equal-length sides. Kites are also known as deltoids, but the word deltoid may also refer to a deltoid curve, an unrelated geometric object sometimes studied in connection with quadrilaterals. A kite may also be called a dart, particularly if it is not convex.

<span class="mw-page-title-main">Tessellation</span> Tiling of a plane in mathematics

A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called tiles, with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of geometries.

<span class="mw-page-title-main">Aperiodic tiling</span> Form of plane tiling in mathematics

An aperiodic tiling is a non-periodic tiling with the additional property that it does not contain arbitrarily large periodic regions or patches. A set of tile-types is aperiodic if copies of these tiles can form only non-periodic tilings.

Hao Wang was a Chinese-American logician, philosopher, mathematician, and commentator on Kurt Gödel.

<span class="mw-page-title-main">Robert Ammann</span> American mathematician

Robert Ammann was an amateur mathematician who made several significant and groundbreaking contributions to the theory of quasicrystals and aperiodic tilings.

Robert Berger is an applied mathematician, known for discovering the first aperiodic tiling using a set of 20,426 distinct tile shapes.

In computability theory and computational complexity theory, RE is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem.

<span class="mw-page-title-main">Jarkko Kari</span> Finnish mathematician and computer scientist

Jarkko J. Kari is a Finnish mathematician and computer scientist, known for his contributions to the theory of Wang tiles and cellular automata. Kari is currently a professor at the Department of Mathematics, University of Turku.

In mathematics, a domino is a polyomino of order 2, that is, a polygon in the plane made of two equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to be distinct shapes, there is only one free domino.

<span class="mw-page-title-main">Penrose tiling</span> Non-periodic tiling of the plane

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 a tiling is aperiodic if it does not contain arbitrarily large periodic regions or patches. However, despite their lack of translational symmetry, Penrose tilings may have both reflection symmetry and fivefold rotational symmetry. Penrose tilings are named after mathematician and physicist Roger Penrose, who investigated them in the 1970s.

<span class="mw-page-title-main">Reversible cellular automaton</span> Cellular automaton that can be run backwards

A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.

<span class="mw-page-title-main">Keller's conjecture</span> Geometry problem on tiling by hypercubes

In geometry, Keller's conjecture is the conjecture that in any tiling of n-dimensional Euclidean space by identical hypercubes, there are two hypercubes that share an entire (n − 1)-dimensional face with each other. For instance, in any tiling of the plane by identical squares, some two squares must share an entire edge, as they do in the illustration.

<span class="mw-page-title-main">Pythagorean tiling</span> Tiling by squares of two sizes

A Pythagorean tiling or two squares tessellation is a tiling of a Euclidean plane by squares of two different sizes, in which each square touches four squares of the other size on its four sides. Many proofs of the Pythagorean theorem are based on it, explaining its name. It is commonly used as a pattern for floor tiles. When used for this, it is also known as a hopscotch pattern or pinwheel pattern, but it should not be confused with the mathematical pinwheel tiling, an unrelated pattern.

<span class="mw-page-title-main">Aperiodic set of prototiles</span>

A set of prototiles is aperiodic if copies of the prototiles can be assembled to create tilings, such that all possible tessellation patterns are non-periodic. The aperiodicity referred to is a property of the particular set of prototiles; the various resulting tilings themselves are just non-periodic.

<span class="mw-page-title-main">Einstein problem</span> Question about single-shape aperiodic tiling

In plane geometry, the einstein problem asks about the existence of a single prototile that by itself forms an aperiodic set of prototiles; that is, a shape that can tessellate space but only in a nonperiodic way. Such a shape is called an einstein, a word play on ein Stein, German for "one stone".

In mathematical logic, a first-order language of the real numbers is the set of all well-formed sentences of first-order logic that involve universal and existential quantifiers and logical combinations of equalities and inequalities of expressions over real variables. The corresponding first-order theory is the set of sentences that are actually true of the real numbers. There are several different such theories, with different expressive power, depending on the primitive operations that are allowed to be used in the expression. A fundamental question in the study of these theories is whether they are decidable: that is, is there an algorithm that can take a sentence as input and produce as output an answer "yes" or "no" to the question of whether the sentence is true in the theory.

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 , 213 (5): 98–106, doi:10.1038/scientificamerican1165-98 . 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, JSTOR   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 (3): 177–209, Bibcode:1971InMat..12..177R, doi:10.1007/bf01418780, MR   0297572, S2CID   14259496 .
  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, Michaël (2021), "An aperiodic set of 11 Wang tiles", Advances in Combinatorics: 1:1–1:37, arXiv: 1506.06492 , doi:10.19086/aic.18614, MR   4210631, S2CID   13261182 . (Showed an aperiodic set of 11 tiles with 4 colors, and proved that fewer tiles or fewer colors cannot be aperiodic.)
  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 (6693): 539–544, Bibcode:1998Natur.394..539W, doi:10.1038/28998, PMID   9707114, S2CID   4385579 .
  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. Neyret, Fabrice; Cani, Marie-Paule (1999), "Pattern-Based Texturing Revisited", Proceedings of the 26th annual conference on Computer graphics and interactive techniques - SIGGRAPH '99 (PDF), Los Angeles, United States: ACM, pp. 235–242, doi:10.1145/311535.311561, ISBN   0-201-48560-5, S2CID   11247905 . Introduces stochastic tiling.
  14. Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), "Wang tiles for image and texture generation", ACM SIGGRAPH 2003 Papers on - SIGGRAPH '03 (PDF), New York, NY, USA: ACM, pp. 287–294, doi:10.1145/1201775.882265, ISBN   1-58113-709-5, S2CID   207162102, archived from the original (PDF) on 2006-03-18.
  15. 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, S2CID   53224612 . Applies Wang Tiles for real-time texturing on a GPU.
  16. . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006), "Recursive Wang tiles for real-time blue noise", ACM SIGGRAPH 2006 Papers on - SIGGRAPH '06, New York, NY, USA: ACM, pp. 509–518, doi:10.1145/1179352.1141916, ISBN   1-59593-364-6, S2CID   11007853 . Shows advanced applications.
  17. Kari, Jarkko (1990), "Reversibility of 2D cellular automata is undecidable", Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena, vol. 45, pp. 379–385, Bibcode:1990PhyD...45..379K, doi:10.1016/0167-2789(90)90195-U, MR   1094882 .
  18. Burnham, Karen (2014), Greg Egan, Modern Masters of Science Fiction, University of Illinois Press, pp. 72–73, ISBN   978-0-252-09629-7 .

Further reading