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
Famous quotes containing the word history:
“Hence poetry is something more philosophic and of graver import than history, since its statements are rather of the nature of universals, whereas those of history are singulars.”
—Aristotle (384–322 B.C.)
“While the Republic has already acquired a history world-wide, America is still unsettled and unexplored. Like the English in New Holland, we live only on the shores of a continent even yet, and hardly know where the rivers come from which float our navy.”
—Henry David Thoreau (1817–1862)
“What is most interesting and valuable in it, however, is not the materials for the history of Pontiac, or Braddock, or the Northwest, which it furnishes; not the annals of the country, but the natural facts, or perennials, which are ever without date. When out of history the truth shall be extracted, it will have shed its dates like withered leaves.”
—Henry David Thoreau (1817–1862)