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.