Wang tile

Wang tiles (or Wang dominoes ), designed in 1961 by Wang Hao, are groups of equal size rectangles whose edges are each marked with a specific color. Such a group of tiles represents an instance of an undecidable decision problem Represents the following figure shows a set of 13 Wang tiles:

The problem to be solved or the decision problem is to decide whether it is possible with a given finite set of tiles to the level of a parquet. This means that any number of copies of tiles from the sentence completely to fill the unlimited plane so that it used all tiles abut each with sides of equal color. The tiles must not be rotated or mirrored.

Wang proposed an algorithm in 1961, which should solve this problem. In the proof of the correctness of his trial he assumed that each set of tiles that fill the plane, this would parqueting it periodically.

1966 shows Robert Berger, however, that Wang's conjecture was wrong. He gave this to a set of Wang tiles, with which one could tile the surface only aperiodic. With these tiles you can indeed fill the plane without gaps, but not so that this surface is filled by a periodically repetitive finite neckline. This is similar to the situation in the Penrose tiling or the arrangement of atoms in quasi- crystals. Although Berger originally used a set of 20 526 tiles, he suspected that a smaller number of tiles with this property would also be possible. In the following years, smaller sets were always found tiles. For example, pictured above group of 13 tiles is published by Karel Culik aperiodic set.

Wang's algorithm for deciding whether a given set of tiles parquetted the plane, that was not correct. In fact, such an algorithm does not exist. It is possible to translate any Turing machine in such a manner in a set of Wang tiles, these tiles the plane if and only parqueting if the Turing machine may not stop. Because the halting problem is undecidable, even the Kachelungsproblem Wang is not decidable. Conversely, the problem is semi- determinable whether a tiling is not possible. A corresponding algorithm goes through all finite subsets of the plane and only needs to recognize that it is not possible for such a tiling. In summary, over the Nichtparkettierbarkeit with a set of tiles with the same problems to solve as a Turing machine. Precise: The problem is with respect to the many-one reduction of a complete semi- decidable problem.

The fact that Wang's method is not applicable in principle to any tile sets, this does not useless for practical applications. With an optimized version of the original method Segio Demian learner was able to show that there are no aperiodic tile sets with seven or fewer tiles. This lower limit can be 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 equal cubes with colored areas. Culik and Kari who may have aperiodic sets of Wang Cubes.

Wang tiles are suitable because of its simplicity for making simple models or models that have the same output power as Turing machines. Winfree et al. have the manufacturability of molecular "tiles" of deoxyribonucleic acid (DNA) demonstrated that one can use as the Wang tiles. Mittal et al. have the same shown for PNA ( peptide nucleic acid ), a chemical variant of the DNA.