Aperiodic tiling
An aperiodic tiling is a tiling of an infinite space with tessellating shapes that is not invariant under any translational symmetry. In particular, sets of shape exist that tile the plane but only in an aperiodic manner, the most famous being the Penrose tiling.
Wang tiles are sets of squares (which aren't allowed to be rotated or reflected), which are only allowed to tessellate in a way that joins all edges to others of the same colour. Jeandel-Rao[1] proved that 11 tiles and 4 colours are the respective minimums necessary for a Wang tile set to force aperiodicity, and exhibited an example set meeting both minimums at once.
On May 5, 2016, NotLiving found an encoding of the Jeandel-Rao set into 8 × 8 Life patterns, that may tile the plane as a still life, but only aperiodically.[2]
On August 20, 2023, Ville Salo and Ilkka Törmä found a pattern which forms a rectangular 6210 × 37800 agar, containing wires whose preimages must be on and off satisfying circuitry, whch simulates the constratints of the Jeandel-Rao set.[3]
Determining whether a set can tile the plane is in general undecidable, meaning that determining whether an arbitrary periodic agar has a predecessor is also.
See also
References
- ↑ Emmanuel Jeandel, Michael Rao (June 22, 2015). An aperiodic set of 11 Wang tiles
- ↑ NotLiving (May 5, 2016). SAT solvers as searchers and Wang tiles (discussion thread) at the ConwayLife.com forums
- ↑ Ville Salo, Ilkka Törmä (August 20, 2023). Computing backwards with Game of Life, part 1: wires and circuits