Wang tile

Wang tiles (or Wang dominoes), first proposed by Hao Wang[?] in 1961, are equal-sized squares with a color on each edge which give rise to a simple undecidable problem. The following shows an example set of 13 Wang tiles:

The standard question is whether a given finite set can tile the plane. This means that copies of the tiles can be arranged to fill an infinite plane, such that contiguous edges always have the same color. The tiles cannot be rotated or reflected.

In 1961, Wang proposed an algorithm to take any finite set of tiles and decide whether they tiled the plane. To prove his algorithm worked, he had to make one assumption. He assumed any set that could tile the plane, would be able to tile the plane periodically (with a pattern that repeats, like standard wallpaper).

However, in 1966 Robert Berger[?] proved Wang's conjecture was wrong. He presented a set of Wang tiles that could only tile the plane aperiodically. This meant it could fill the plane without holes, but the tiling couldn't be a simple repitition of a finite pattern. 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 hypothesized that smaller sets would work, including subsets of his set. In later years, increasingly smaller sets were found. For example, the set of 13 tiles given above is an aperiodic set published by Karel Culik. It can tile the plane, but not periodically.

Wang's algorithm for determining whether a set of tiles can tile the plane was not correct. In fact, no such algorithm can exist. It is possible to translate any Turing machine into a set of Wang tiles, such that the Wang tiles can tile the plane if and only if the Turing machine will never halt. The halting problem is uncomputable, therefore the Wang tiling problem is also uncomputable. In a sense, Wang tiles have computational power equivalent to that of a Turing machine.

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. Culik and Kari have demonstrated aperiodic sets of Wang cubes. Seeman et. al. have demonstrated the feasability 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 PNA (peptide nucleic acid), a stable artificial mimic of DNA.

External links and references

• Wang, H. (1961), Bell System Tech. Journal 40(1961), pp. 1-42. (Wang proposes his tiles, and hypothesizes there are no aperiodic sets).
• Wang, H. (1965) "Games, logic and computers" in Scientific American, Nov. 1965, pp. 98-106. (Presents them for a popular audience)
• Berger, R. (1966), "The undecidability of the domino problem", Memoirs Amer. Math. Soc. 66(1966). (Coins the term "Wang tiles", and demonstrates the first aperiodic set of them).
• Culik, K. (1996), "An aperiodic set of 13 Wang tiles", Discrete Applied Mathematics 160, 245-251. (download (ftp://ftp.cs.sc.edu/pub/culik/tiles.ps.gz)) (Showed an aperiodic set of 13 tiles with 5 colors).
• Culik, K., and K. Kari (1995), "An aperiodic set of Wang cubes", Journal of Universal Computer Science 1, 675-686 (1995).
• Steven Dutch's page including many pictures of aperiodic tilings (http://www.uwgb.edu/dutchs/symmetry/aperiod.htm)
• Winfree, E., Liu, F., Wenzler, L.A., and Seeman, N.C. (1998) “Design and Self-Assembly of Two-Dimensional DNA Crystals, Nature 394, 539-544.
• Lukeman, P., Seeman, N. and Mittal, A. “Hybrid PNA/DNA Nanosystems.” (2002) In 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii.