Wang tiling

from Wikipedia, the free encyclopedia

Wang tiles (or Wang Domino ), designed by Hao Wang in 1961 , are groups of rectangles of the same size, the edges of which are each marked with a certain color. Such a group of tiles represents an instance of an un decidable is the decision problem The figure below shows a set of 13 Wang tiles.:

Wang tiles.svg

The task to be solved or the decision problem is to decide whether it is possible with a given finite set of tiles to parquet the level . This means using any number of copies of the tiles from the set to fill the unlimited level without gaps in such a way that all the tiles used come together with sides of the same color. The tiles must not be twisted or mirrored.

Wang proposed an algorithm in 1961 that would solve this problem. In proving the correctness of his procedure, he assumed that any set of tiles filling the plane would periodically parquet it.

Section of aperiodic tiling of the plane

In 1966, however, Robert Berger shows that Wang's guess was wrong. He gave a set of Wang tiles with which the area could only be tiled aperiodically . These tiles can be used to fill the level without gaps, but not in such a way that the area is filled by a finite section that repeats itself periodically. This is similar to the situation with the Penrose tiling or the arrangement of the atoms in quasi-crystals . Although Berger originally used a set of 20,426 tiles, he suspected that fewer tiles with this property would also be possible. In the years that followed, smaller and smaller sets of tiles were found. For example, the group of 13 tiles shown above is an aperiodic set published by Karel Culik.

Wang's algorithm for deciding whether a given set of tiles tiled the level was not correct. Indeed, such an algorithm does not exist. It is possible to translate every Turing machine into a set of Wang tiles in such a way that these tiles parquet the plane exactly when the Turing machine does not stop. Since the holding problem is not decidable, Wang's tiling problem is not decidable either. Conversely, the problem is semi-decidable , whether tiling is not possible. A corresponding algorithm goes through all finite subsets of the level and only needs to recognize that such a tiling is not possible. In summary, the same problems can be solved by not being able to parquet with a set of tiles as with a Turing machine. Precise: With regard to the many-one reduction, the problem is a completely semi-decidable problem.

The fact that Wang's method cannot in principle be applied to any tile set does not make it useless for practical applications. With an optimized version of the original method, Sergio Demian Lerner was able to show that there are no aperiodic tile sets with seven or fewer tiles. This lower limit leaves only a small gap for improvement.

Wang tiles can be generalized in many different ways, all of which are undecidable in the above sense. For example, Wang cubes are cubes of equal size with colored faces. Culik and Kari have aperiodic sets of Wang cubes.

Because of their simplicity, Wang's tiles are suitable for the production of the simplest machines or models that have the same power as Turing machines. Winfree et al. have demonstrated the manufacturability of molecular "tiles" from deoxyribonucleic acid (DNA), which can be used as Wang tiles. Mittal et al. showed the same thing for PNA ( peptide nucleic acid ), a chemical variant of DNA.

See also

Commons : Wang tiles  - collection of images, videos and audio files

literature

  • Hao Wang: Proving theorems by pattern recognition. Part II. In: Bell System Technical Journal. 40, pp. 1-42 (1961). (Wang introduces his tiles and assumes that there is no aperiodic tiling).
  • Hao Wang: Games, logic and computers. In: Scientific American . November 1965, pp. 98-106. (Introduces them to a wider public)
  • Robert Berger: The undecidability of the domino problem. Memoirs of the American Mathematical Society Number 66. AMS Bookstore, Providence (RI) 1966, ISBN 0-8218-1266-1 . (Coined the expression "Wang tiles", and introduces the first aperiodic set of tiles).
  • Karel Culik II: An aperiodic set of 13 Wang tiles . In: Discrete Applied Mathematics. 160, 245-251. (Shows an aperiodic set of 13 tiles with 5 colors).
  • Karel Culik II & Jarkko Kari: An aperiodic set of Wang cubes. In: Journal of Universal Computer Science. 1 (1995), pp. 675-686. ( PDF; 193 KB )
  • Erik Winfree, Furong Liu, Lisa A. Wenzler & Nadrian C. Seeman: Design and Self-Assembly of Two-Dimensional DNA Crystals. In: Nature . 394: 539-544 (1998). ( PDF; 734 KB )
  • Philip S. Lukeman, Nadrian C. Seeman & Alexander C. Mittal: Hybrid PNA / DNA Nanosystems. In: First International Conference on Nanoscale / Molecular Mechanics (N-M2-I). Outrigger Wailea Resort, Maui, Hawaii, 2002

Web links