Crystallography & Symmetry
patterns derived from their groups
Concept

Wang tile — where it appears

A unit square with a colour on each edge, laid edge to edge with matching colours and never turned or reflected. Whether a given finite set of them tiles the plane is undecidable, and the smallest set that tiles only aperiodically has eleven tiles and four colours.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

8 tiles over 5 colours. Wang tiles: unit squares with a colour on each edge, which may be laid side by side only where the touching edges agree, and which may never be turned or reflected. That last restriction is what makes them a computational object rather than a jigsaw — an edge colour is a symbol passed from one tile to its neighbour, and turning a tile would let a symbol change direction. The set here was generated from a stated seed.

Nothing decides whether a set of tiles tiles the plane

This collection rests on decidability — generate a pattern, forget the group, rediscover it, compare. One question in the same subject has no procedure at all: given a finite set of tiles, whether they cover the plane cannot be decided by any algorithm whatever. What can be done is two half-searches, and measuring what they leave behind.

classification · Decidability 656 sets, every one decided. Every set of one, two, three and four tiles over two colours — sixteen tiles exist in all, so these are complete lists rather than samples — reduced by relabelling the two colour alphabets, and each set decided by the two half-searches. The last column is the one that matters: it is empty. At these sizes there is no room for a set that tiles the plane and admits no periodic tiling, which is the residue undecidability lives in. The smallest aperiodic set is known to have eleven tiles and four colours.

How much room a hard question needs

No algorithm decides whether a set of tiles covers the plane. Every set of four or fewer tiles over two colours is nevertheless decided here, exhaustively, in under a second — because the sets that defeat the two half-searches have nowhere small to live.

classification · Decidability

Named alongside it

The objects these essays reach for when they reach for this one.

AperiodicityDecidabilityAperiodic tile setCertificateExhaustive searchLocal rulesMatching rulesSemi decisionTiling by a group

All concepts