Penrose tiling

A Penrose tiling is an example of non-periodic tiling generated by an aperiodic set of prototiles. Penrose tilings are named after mathematician and physicist Roger Penrose, who investigated these sets in the 1970s. The aperiodicity of prototiles implies that a shifted copy of a tiling will never match the original. A Penrose tiling may be constructed so as to exhibit both reflection symmetry and fivefold rotational symmetry, as in the diagram at the right. A Penrose tiling is an example of non-periodic tiling generated by an aperiodic set of prototiles. Penrose tilings are named after mathematician and physicist Roger Penrose, who investigated these sets in the 1970s. The aperiodicity of prototiles implies that a shifted copy of a tiling will never match the original. A Penrose tiling may be constructed so as to exhibit both reflection symmetry and fivefold rotational symmetry, as in the diagram at the right. Penrose tiling is non-periodic, which means that it lacks any translational symmetry. It is self-similar, so the same patterns occur at larger and larger scales. Thus, the tiling can be obtained through 'inflation' (or 'deflation') and every finite patch from the tiling occurs infinitely many times. It is a quasicrystal: implemented as a physical structure a Penrose tiling will produce Bragg diffraction and its diffractogram reveals both the fivefold symmetry and the underlying long range order. Various methods to construct Penrose tilings have been discovered, including matching rules, substitutions or subdivision rules, cut and project schemes and coverings. Penrose tilings are simple examples of aperiodic tilings of the plane. A tiling is a covering of the plane by tiles with no overlaps or gaps; the tiles normally have a finite number of shapes, called prototiles, and a set of prototiles is said to admit a tiling or tile the plane if there is a tiling of the plane using only tiles congruent to these prototiles. The most familiar tilings (e.g., by squares or triangles) are periodic: a perfect copy of the tiling can be obtained by translating all of the tiles by a fixed distance in a given direction. Such a translation is called a period of the tiling; more informally, this means that a finite region of the tiling repeats itself in periodic intervals. If a tiling has no periods it is said to be non-periodic. A set of prototiles is said to be aperiodic if it tiles the plane but every such tiling is non-periodic; tilings by aperiodic sets of prototiles are called aperiodic tilings. The subject of aperiodic tilings received new interest in the 1960s when logician Hao Wang noted connections between decision problems and tilings. In particular, he introduced tilings by square plates with colored edges, now known as Wang dominoes or tiles, and posed the 'Domino Problem': to determine whether a given set of Wang dominoes could tile the plane with matching colors on adjacent domino edges. He observed that if this problem were undecidable, then there would have to exist an aperiodic set of Wang dominoes. At the time, this seemed implausible, so Wang conjectured no such set could exist. Wang's student Robert Berger proved that the Domino Problem was undecidable (so Wang's conjecture was incorrect) in his 1964 thesis, and obtained an aperiodic set of 20426 Wang dominoes. He also described a reduction to 104 such prototiles; the latter did not appear in his published monograph, but in 1968, Donald Knuth detailed a modification of Berger's set requiring only 92 dominoes. The color matching required in a tiling by Wang dominoes can easily be achieved by modifying the edges of the tiles like jigsaw puzzle pieces so that they can fit together only as prescribed by the edge colorings. Raphael Robinson, in a 1971 paper which simplified Berger's techniques and undecidability proof, used this technique to obtain an aperiodic set of just six prototiles.