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)

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.

Smaller Sets

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.

Bibliography