Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Wang tile
Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, is a class of formal systems. They are modeled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them.
The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The next question is whether this can be done in a periodic pattern.
In 1961, Wang conjectured that if a finite set of Wang tiles can tile the plane, then there also exists a periodic tiling, which, mathematically, is a tiling that is invariant under translations by vectors in a 2-dimensional lattice. This can be likened to the periodic tiling in a wallpaper pattern, where the overall pattern is a repetition of some smaller pattern. He also observed that this conjecture would imply the existence of an algorithm to decide whether a given finite set of Wang tiles can tile the plane. The idea of constraining adjacent tiles to match each other occurs in the game of dominoes, so Wang tiles are also known as Wang dominoes. The algorithmic problem of determining whether a tile set can tile the plane became known as the domino problem.
According to Wang's student, Robert Berger,
The Domino Problem deals with the class of all domino sets. It consists of deciding, for each domino set, whether or not it is solvable. We say that the Domino Problem is decidable or undecidable according to whether there exists or does not exist an algorithm which, given the specifications of an arbitrary domino set, will decide whether or not the set is solvable.
In other words, the domino problem asks whether there is an effective procedure that correctly settles the problem for all given domino sets.
In 1966, Berger solved the domino problem in the negative. He proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem (the problem of testing whether a Turing machine eventually halts) then implies the undecidability of Wang's tiling problem.
Combining Berger's undecidability result with Wang's observation shows that there must exist a finite set of Wang tiles that tiles the plane, but only aperiodically. This is similar to a Penrose tiling, or the arrangement of atoms in a quasicrystal. Although Berger's original set contained 20,426 tiles, he conjectured that smaller sets would work, including subsets of his set, and in his unpublished Ph.D. thesis, he reduced the number of tiles to 104. In later years, ever smaller sets were found. For example, a set of 13 aperiodic tiles was published by Karel Culik II in 1996.
Hub AI
Wang tile AI simulator
(@Wang tile_simulator)
Wang tile
Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, is a class of formal systems. They are modeled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them.
The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The next question is whether this can be done in a periodic pattern.
In 1961, Wang conjectured that if a finite set of Wang tiles can tile the plane, then there also exists a periodic tiling, which, mathematically, is a tiling that is invariant under translations by vectors in a 2-dimensional lattice. This can be likened to the periodic tiling in a wallpaper pattern, where the overall pattern is a repetition of some smaller pattern. He also observed that this conjecture would imply the existence of an algorithm to decide whether a given finite set of Wang tiles can tile the plane. The idea of constraining adjacent tiles to match each other occurs in the game of dominoes, so Wang tiles are also known as Wang dominoes. The algorithmic problem of determining whether a tile set can tile the plane became known as the domino problem.
According to Wang's student, Robert Berger,
The Domino Problem deals with the class of all domino sets. It consists of deciding, for each domino set, whether or not it is solvable. We say that the Domino Problem is decidable or undecidable according to whether there exists or does not exist an algorithm which, given the specifications of an arbitrary domino set, will decide whether or not the set is solvable.
In other words, the domino problem asks whether there is an effective procedure that correctly settles the problem for all given domino sets.
In 1966, Berger solved the domino problem in the negative. He proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem (the problem of testing whether a Turing machine eventually halts) then implies the undecidability of Wang's tiling problem.
Combining Berger's undecidability result with Wang's observation shows that there must exist a finite set of Wang tiles that tiles the plane, but only aperiodically. This is similar to a Penrose tiling, or the arrangement of atoms in a quasicrystal. Although Berger's original set contained 20,426 tiles, he conjectured that smaller sets would work, including subsets of his set, and in his unpublished Ph.D. thesis, he reduced the number of tiles to 104. In later years, ever smaller sets were found. For example, a set of 13 aperiodic tiles was published by Karel Culik II in 1996.