Wang originally conjectured that no aperiodic tilings could exist. Wang was interested in the decidability of the Tiling Problem; it is said to be decidable if there exists an algorithm which will yield a solution for any given set of prototiles in a finite number of steps or trials. The following is a simplified version of his approach (Grünbaum and Shephard 1987, page 602).
If a set of prototiles admits a tiling then one of these possibilities must hold:
(a) the set admits only periodic tilings, for example just one regular hexagon.
(b) the set admits periodic and non-periodic tilings, for example a square.
(c) the set admits only non-periodic tilings, in other words is an aperiodic set.
Wang showed that the Tiling Problem is decidable if one only considers sets which satisfy (a) and (b). In 1961 he went on to conjecture that possibility (c) could not occur, at the time an entirely plausible assertion.
The discovery of an aperiodic set spoilt Wang’s argument and it is now known that the Tiling Problem is undecidable.
The first aperiodic set was found by Wang’s student Berger (1966) and consisted of 20,426 tiles. This was first reduced by Berger to 104 tiles, then by Knuth to 96.
Other aperiodic tilings have since been used to produce smaller sets of aperiodic Wang tiles, from 32 to 24 and 16 as shown below.
According to Grünbaum and Shephard (Grünbaum and Shephard 1987, page 596).
“The reduction in the number of Wang tiles in an aperiodic set from over 20,000 to 16 has been a notable achievement. Perhaps the minimum possible number has now been reached. If, however, further reductions are possible then it seems certain that new ideas and methods will be required.”
Kari suggested such a method and produced a set of 14 tiles over 6 colours (Kari 1996). This was reduced by Culik to 13 tiles over 5 colours (Culik 1998) and this appears to be the smallest known set, although together they have attempted to show that one tile can be removed from the set.
However for Architectural and Computer Graphics applications the smallest set is not necessarily the most desirable.
Penrose P2 to Wang Tiling (32 Tiles)
A set of 32 Wang tiles can be generated from an aperiodic Penrose P2 tiling. The following procedure was suggested by Penrose and refined by Robinson. It starts with a Penrose P2 tiling such as that below, although Grünbaum and Shephard suggest the procedure could be simplified by using a Penrose P3 Rhomb tiling.
1. Grid the Penrose Tiling
Cut up the Penrose P2 tiling by keeping as close to the horizontal and vertical as possible. In fact each patch is made up of Robinson’s A-tiles (kites, darts, half-kites and half-darts).
2. Catalogue the Cut-Up Shapes
Catalogue the cut-up shapes using the dot and arrow matching rule for Penrose P2 Tiling (each type of dot must match and arrows be in same direction).
3. Assign Colours to Edges of Cut-Up Shapes
Using the following colours
Assign colours to vertical and horizontal edges respecting and the encoding by dots and arrows as follows:-
4. Assign A Wang Tile to Each Cut-Up Shape
Assign Wang tiles to each of the cut-up shapes including their rotations and reflections using the encoded edge colours. The rotations and reflections are required because Wang tiles do not permit rotation or reflection.
5. Assign Appropriate Wang Tiles
Replace the gridded P2 Tiling with the corresponding Wang tiles:-
This is the Wang tile equivalent of the original Penrose P2 tiling shown at the the start of this section, using 32 tiles over 16 colours.
Ammann A2 to Wang Tiling (24 Tiles)
Ammann A2 tiles can have unit length sides, so the prototiles can be made up of collections of 3 squares and 5 squares.
Because Wang tiles cannot be rotated or mirrored each of the possible orientations of the A2 prototypes needs to have its own unique set of Wang tiles.
1. Create a Set of 24 Wang Tiles Using 24 Colours
The 24 colours on the left are used to generate the 24 unique Wang tiles on the right.
2. Map the 24 Wang Tiles onto 8 Prototiles
The Wang tiles are then mapped onto the 4 possible orientations of Ammann A2 prototiles (8 tiles in all as listed in the diagram below).
As indicated by the orientation of the coloured triangles in the colour list above, the first row of colours is used on the top and bottom edges of the Wang and A2 prototiles; these both have to match other tiles edge to edge. Similarly the second row of colours is used on the left and right hand edges of both sets of tiles.
The third and fourth rows are used for the top and bottom edges of the Wang tiles that become the internal edges of the A2 prototiles.
Rows five and six are used for the left and right hand internal edges of the A2 prototiles.
The functional arrangement of the colours above differs from Grünbaum and Shephard, but the numbers above and below them are those that they used.
3. Allow Duplication Between 3 and 5 Square Prototiles
The red numbered Wang tiles in the prototile catalogue represent the tiles that are used in both the 5 and 3 square A2 prototiles and allowing these duplications allows the number of Wang tiles to be reduced to 24.
Ammann A2 to Wang Tiling (16 Tiles)
A sets of 16 Wang tiles can be generated from the Golden Section version of the same aperiodic Ammann A2 tiling marked with 2 sets of parallel Ammann bars. These form overlapping red and cyan grids.
1. Catalogue the Tiles formed by the Cyan Grid
Using the cyan grid to provide the edges of a new set of tiles and the red grid to create the markings that provide the matching conditions, catalogue the different tile types (outlined in blue and numbered below).
According to Grünbaum and Shephard this results in the following 16 tiles (although tile 6 does not appear to be present above)
2. Map the Catalogued Tiles to Wang Tiles
Map the 16 catalogued tiles above to the 16 Wang tiles below using 6 colours.
A further set of tiles can be generated that correspond to composed or decomposed versions of the tiles above.
3. Apply the Wang Tiles to the Original Tiling
A Wang tiling can then be generated that corresponds to the original Golden Section Ammann A2 tiling using 16 tiles over 6 colours and with the composed tiling indicated by thickened lines.
More recently smaller sets of Wang tiles have been found using an entirely different method due to Kari, (Kari 1996). This uses Mealy machines that multiply Beatty sequences of real numbers by rational constants. Using this method Kari produced a tile set of 14 tiles over 6 colours. Using a slightly modified version of Kari’s method Culik, Culik 1996, produced a set of 13 tiles over 5 colours.
The authors propose the following 13 over 5 colour Wang tile set.
Wonderful post. I have been readiing it extensively along with the Grunbaum and Shepard book. Quick question. For the P2 transfer to wang tiles, you write “Cut up the Penrose P2 tiling by keeping as close to the horizontal and vertical as possible. ”
It exercise 11.1.4 in the G & S book, they suggestis an approach to cutting up the tiling.
I would like to generate the tiling algorithmically, but cannot for the life of me figure out completely either your method or the method they suggest.
Any help would be much appreciated.
Thanks in advance,
Good article. However you must update your article to include the smallest set of 11 Wang tiles https://arxiv.org/abs/1506.06492
Thanks for the information.
I will update post shortly.
This blog was… how do I say it? Relevant!! Finally I’ve
found something which helped me. Thank you!
Monsters move as they sing, meaning your island is sooner or
later complete of gorgeous creatures all singing and
moving in one particular large harmony.
I think the whole idea of using Wang tiles, or other aperiodic tiles, is to have a feeling of tight local order and loose overall randomness. In musical terms I am not sure which parts the colours and tiles take.
In the post different combinations are illustrated:
32 tiles in 16 colours (from Penrose P2), 24 tiles in 24 colours (Ammann A2), 16 tiles in 6 colours (Golden Section A2), 14 in 6 (Kari) and 13 in 5 Culic. Whilst mathematically the aim seems to be the minimum number of tiles and colours, visually, and I suspect musically, the larger number of tiles seem to be more satisfying.
A completely different take is given here
If you rotate things through 45 degrees, each Wang tile has two triangles above the horizontal and 2 below. These can be thought of as two layers of musical ideas, running in counterpoint – the primary one at the top, the secondary one underneath. Each colour could represent a different musical idea.
The counterpoint would need to be invertible. But it would not be necessary for all the different ideas (colours) to work with each other simultaneously.
The music would be performed by playing the music associated with the Wang tile, plus (as a subordinate, maybe quieter) the two touching tiles above and below the Wang tile. The performer then moves from tile to tile, with the music changing seamlessly as it does so
Imagine a person playing a computer game – the person’s location within the game could be used to trigger the associated Wang tiles music, giving a feeling of cohesion without any obvious periodic looping.
Hello, after reading this amazing piece of writing i am also happy to share my knowledge here with
I have read so many psts regarding the blogger lovers but
this article is actually a pleasant paragraph, keep itt up.
I have read so many articles or reviews concerning the blogger lovers but this paragraph is actually a
good article, keep it up.
Do you know how to turn a first-order logic well-formed formula without functions and equality into a Kahr-Wang-Moore formula with the Wang tiles? I would like to know where to learn how to do this. Thank you. My email is firstname.lastname@example.org
Pingback: Wang Tiles and Aperiodic Tiling | ESALA