On aperiodic sets of Wang tiles (Q4371018)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1101596
Language Label Description Also known as
default for all languages
No label defined
    English
    On aperiodic sets of Wang tiles
    scientific article; zbMATH DE number 1101596

      Statements

      0 references
      0 references
      22 February 1998
      0 references
      Wang tiles
      0 references
      aperiodic tiling
      0 references
      On aperiodic sets of Wang tiles (English)
      0 references
      Wang tiles are unit square tiles with colored edges oriented horizontally and vertically. Tilings of the Euclidean plane are considered using arbitrarily many translates to integer lattice points of a finite tile set \(T\) of Wang tiles. Such a tiling is called valid if contiguous edges have the same color. A tile set \(T\) is called aperiodic if there exists a valid tiling, but no such valid tiling is periodic. R. Berger, in his proof of the undecidability of the tiling problem, refuted Wang's conjecture that no aperiodic set exists and constructed the first aperiodic set containing 29426 tiles. Between 1966 and 1978 this number was lowered to 16 tiles. Recently the second author constructed a aperiodic set containing 14 tiles over 6 colors, and the first author applied the method to reduce the number to 13 tiles over 5 colors. In this article, they discuss a plan, based on balanced representation of numbers and sequential machines, to find an aperiodic set consisting of just 12 tiles. For the entire collection see [Zbl 0877.00007].
      0 references

      Identifiers