Aperiodic Tiling - History


The second part of Hilbert's eighteenth problem asked for a single polyhedron tiling Euclidean 3-space, such that no tiling by it is isohedral (an anisohedral tile). The problem as stated was solved by Karl Reinhardt (mathematician) in 1928, but aperiodic tilings have been considered as a natural extension.

The specific question of aperiodic tiling first arose in 1961, when logician Hao Wang tried to determine whether the Domino Problem is decidable — that is, whether there exists an algorithm for deciding if a given finite set of prototiles admits a tiling of the plane. Wang found algorithms to enumerate the tilesets that cannot tile the plane, and the tilesets that tile it periodically; by this he showed that such a decision algorithm exists if every finite set of prototiles that admits a tiling of the plane also admits a periodic tiling.

Hence, when in 1966 Robert Berger demonstrated that the tiling problem is in fact not decidable, it followed logically that there must exist an aperiodic set of prototiles. (Thus Wang's procedures do not work on all tile sets, although does not render them useless for practical purposes.) The first such set, presented by Berger and used in his proof of undecidability, required 20,426 Wang tiles. Berger later reduced his set to 104, and Hans Läuchli subsequently found an aperiodic set requiring only 40 Wang tiles. The set of 13 tiles given in the illustration on the right is an aperiodic set published by Karel Culik, II, in 1996.

However, a smaller aperiodic set, of six non-Wang tiles, was discovered by Raphael M. Robinson in 1971. Roger Penrose discovered three more sets in 1973 and 1974, reducing the number of tiles needed to two, and Robert Ammann discovered several new sets in 1977.

In 1988, Peter Schmitt discovered a single aperiodic prototile in 3-dimensional Euclidean space. While no tiling by this prototile admits a translation as a symmetry, it has tilings with a screw symmetry, the combination of a translation and a rotation through an irrational multiple of π. This was subsequently extended by John Horton Conway and Ludwig Danzer to a convex aperiodic prototile, the Schmitt–Conway–Danzer tile. Because of the screw axis symmetry, this resulted in a reevaluation of the requirements for periodicity. Chaim Goodman-Strauss suggested that a protoset be considered strongly aperiodic if it admits no tiling with an infinite cyclic group of symmetries, and that other aperiodic protosets (such as the SCD tile) be called weakly aperiodic.

In 1996 Petra Gummelt showed that a single-marked decagonal tile, with two kinds of overlapping allowed, can force aperiodicity; this overlapping goes beyond the normal notion of tiling. An aperiodic protoset consisting of just one tile in the Euclidean plane, with no overlapping allowed, was proposed in early 2010 by Joshua Socolar; this example requires either matching conditions relating tiles that do not touch, or a disconnected but unmarked tile. The existence of a strongly aperiodic protoset consisting of just one tile in a higher dimension, or of a single simply connected tile in two dimensions without matching conditions, is an unsolved problem.

Read more about this topic:  Aperiodic Tiling

Other articles related to "history":

History of Computing
... The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with or ...
Spain - History - Fall of Muslim Rule and Unification
... The breakup of Al-Andalus into the competing taifa kingdoms helped the long embattled Iberian Christian kingdoms gain the initiative ... The capture of the strategically central city of Toledo in 1085 marked a significant shift in the balance of power in favour of the Christian kingdoms ...
Voltaire - Works - Historical
... History of Charles XII, King of Sweden (1731) The Age of Louis XIV (1751) The Age of Louis XV (1746–1752) Annals of the Empire – Charlemagne, A.D ... on the Manners of Nations (or 'Universal History') (1756) History of the Russian Empire Under Peter the Great (Vol ... II 1763) History of the Parliament of Paris (1769) ...
Casino - History of Gambling Houses
... some form or another has been seen in almost every society in history ... the Ancient Greeks and Romans to Napoleon's France and Elizabethan England, much of history is filled with stories of entertainment based on games of chance ... In American history, early gambling establishments were known as saloons ...
Xia Dynasty - Modern Skepticism
... The Skeptical School of early Chinese history, started by Gu Jiegang in the 1920s, was the first group of scholars within China to seriously question the ... early Chinese history is a tale told and retold for generations, during which new elements were added to the front end" ...

Famous quotes containing the word history:

    The history of the world is none other than the progress of the consciousness of freedom.
    Georg Wilhelm Friedrich Hegel (1770–1831)

    We have need of history in its entirety, not to fall back into it, but to see if we can escape from it.
    José Ortega Y Gasset (1883–1955)

    I assure you that in our next class we will concern ourselves solely with the history of Egypt, and not with the more lurid and non-curricular subject of living mummies.
    Griffin Jay, and Reginald LeBorg. Prof. Norman (Frank Reicher)