%3Cpath d=%22M283.465 94.993l9.555-6.942a7.087 7.087 0 0 1 9.898 1.567l5.217 7.181a7.087 7.087 0 0 0 4.625 2.834c5.5.87 10.999 1.742 16.498 2.613a7.087 7.087 0 0 0 8.108-5.89l1.963-12.398a7.087 7.087 0 0 0-5.89-8.108l-2.5-.396c-6.235-.988-8.164-9.022-3.056-12.733l47.313-34.375 14.81 10.761a5.315 5.315 0 0 1 1.176 7.424l-3.913 5.385a5.315 5.315 0 0 0-.95 3.956l1.96 12.373a5.315 5.315 0 0 0 6.082 4.418l9.298-1.472a5.315 5.315 0 0 0 4.418-6.081l-.297-1.875c-.74-4.676 4.543-7.914 8.374-5.13l50.773 36.888-50.773 36.889c-3.831 2.783-2.385 8.809 2.292 9.55l1.874.296a5.315 5.315 0 0 1 4.418 6.081l-1.472 9.298a5.315 5.315 0 0 1-6.081 4.418l-12.373-1.96a5.315 5.315 0 0 1-3.469-2.125l-3.913-5.385a5.315 5.315 0 0 0-7.424-1.176l-14.81 10.76-47.313-34.374c-5.108-3.711-12.153.606-11.165 6.841l.396 2.5a7.087 7.087 0 0 1-5.891 8.107l-12.398 1.964a7.087 7.087 0 0 1-8.108-5.89l-2.612-16.499a7.087 7.087 0 0 1 1.266-5.274l5.217-7.18a7.087 7.087 0 0 0-1.568-9.899l-9.555-6.942%22 fill=%22%2344c%22 stroke=%22%23000%22/>%3C/svg>">
Paul Harrison @paulfharrison
Wang (1961, section 4.1, A Generalized Game Of Dominos)
Given a set of squares with colored edges, can we tile the plane with copies of these squares so all the edge colors match?
(Rotations and reflections are not allowed.)
Wang's conjecture:
If we can tile the plane, we can do so with a repeating pattern.
Wang's student Berger (1966) showed this is wrong.
There are aperiodic tile-sets.
Berger's initial construction used 20,426 tiles.
The number of tiles needed has been whittled down over time.
Jeandel and Rao (2015) proved the minimum to be 11 tiles:
(Images from paper.)Berger's main application of this was to be able to construct, for any specified Turing machine, a tile-set that contains somewhere within it the Turing machine tape at any number of steps of evaluation. If the Turing machine halts, the tiles will not tile the plane. Since the halting problem is undecidable, knowing in all cases whether a tile-set will tile the plane is also undecidable.
Penrose (1974, patented 1975) found a set of 6 tiles that is aperiodic, and later reduced this to 2 tiles. Roughly, Penrose tiles are obtained by trying to tile the regular pentagon, which does not work and needs further shapes to fill in gaps.
There are several versions of Penrose tiles with only 2 tiles. This variant has thin and fat rhombuses: