Penrose Tilings

Imagine flooring a room of infinite size. You have just two tile shapes — a fat kite and a thin dart — both cut from the same golden rhombus. There is only one rule: where two edges meet, the markings on them must align. That single rule has a striking consequence: the floor can never have a repeating unit. No matter how large a patch you choose, you cannot find a block you could copy and slide to recreate the whole floor.

This phenomenon is called aperiodicity, and Roger Penrose discovered it in 1974. It was shocking at the time, because mathematicians had assumed that any finite set of shapes that tiles the plane must eventually repeat. Penrose proved them wrong with just two tiles.

The pattern looks almost five-fold symmetric — rotate it by $72°$ and it nearly matches itself — but "nearly" is the operative word. True five-fold rotational symmetry is forbidden in ordinary crystals, yet here it appears in the flat plane. That paradox went from mathematical curiosity to physical reality in 1984, when Dan Shechtman discovered real metal alloys whose atoms arranged themselves just like a Penrose tiling — earning him a Nobel Prize in Chemistry in 2011.

The demo below grows a Penrose tiling by inflation: start with a seed arrangement of kites and darts, then repeatedly subdivide each tile into smaller copies following the golden ratio $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$. After each inflation step the tile count grows by a factor of $\varphi^2 \approx 2.618$, filling more of the plane while obeying the matching rules automatically.

<!-- {{c_html_intro}} -->
<div class="controls">
  <button id="btn-inflate" type="button">{{btn_inflate}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="info" id="info">{{lbl_step_0}}</span>
</div>
<canvas id="canvas" width="480" height="420"></canvas>
<p class="hint">{{hint_para}}</p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; background: #f5f7fa; color: #222; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border-radius: 10px; background: #fff;
         box-shadow: 0 2px 10px rgba(0,0,0,.08); max-width: 100%; }
.info { font-size: .88rem; color: #555; margin-left: .3rem; }
.hint { font-size: .82rem; color: #666; margin: .5rem 0 0; line-height: 1.5; }

// Code not found

Notice that no matter how many steps you apply, the same local patches reappear — but never in a globally periodic grid. The golden ratio is woven into the proportions: the ratio of kites to darts in any large tiling converges to exactly $\varphi$.

Penrose tilings are not just pretty — they brush against the hardest questions in computability.

• Local vs. global. Every finite patch of a Penrose tiling can be extended to a full tiling of the plane. But the extension is not unique: uncountably many distinct tilings share any given finite patch. There is no finite algorithm that constructs a single canonical tiling.
• The tiling problem is undecidable. The general question — "given a finite set of tiles with matching rules, can they tile the plane?" — was proved undecidable by Robert Berger in 1966. The proof works by encoding Turing machines into tile sets; a tiling exists if and only if the machine never halts. This is the same wall as the halting problem.
• Aperiodicity and undecidability are linked. Berger also proved that any undecidable tile set must include an aperiodic subset. Penrose's two-tile set is essentially the smallest known aperiodic set (Wang and others needed hundreds of tiles before Penrose cut it to two).
• Local matching rules, global order. The matching rules are entirely local — you only need to look at a single edge — yet they force a globally aperiodic structure that encodes $\log_2 \varphi \approx 0.694$ bits of information per tile. No local rule can distinguish where in the infinite tiling any patch sits.

The punchline: you can check in constant time whether two edges match, but you cannot decide in finite time whether an arbitrary patch can be completed — the global question is strictly harder than any Turing machine can solve.

The mathematics of aperiodic tilings has escaped the blackboard and entered the lab:

• Quasicrystals: the 1984 discovery by Dan Shechtman showed that aluminium-manganese alloys diffract X-rays with sharp peaks and five-fold symmetry — the physical fingerprint of Penrose-like atomic order. The 2011 Nobel Prize validated what mathematicians already knew.
• Photonics: aperiodic structures scatter light at many angles simultaneously. Penrose-inspired photonic crystals open bandgaps that periodic lattices cannot, enabling ultra-compact optical filters and LEDs.
• Antenna arrays: arranging antenna elements on a Penrose grid suppresses grating lobes that plague periodic arrays, improving radar and wireless coverage.
• Cryptography and watermarking: the non-periodic yet deterministic structure of Penrose tilings has been proposed as a base for visual watermarking and pseudo-random number generation.
• Teaching undecidability: the tiling problem is one of the clearest introductions to problems that are provably beyond any algorithm — the same wall as the halting problem.

Understand Penrose tilings and you've glimpsed how local rules can force global structure that no finite algorithm can fully capture.

Two humble shapes — a kite and a dart — hide a universe of mathematical depth. Their matching rule is trivially checkable at every edge, yet the global question of whether a patch can tile the whole plane is provably undecidable. The golden ratio $\varphi$ weaves through every proportion, and five-fold symmetry blooms from a rule that forbids it at the local level.

Penrose tilings remind us that local simplicity does not imply global predictability. The same lesson echoes across computer science: easy-to-check rules can generate questions that no algorithm can ever resolve — just as in the halting problem. Meanwhile, the real world has built quasicrystals, photonic devices, and better antennas from the same ideas.

The floor that can never repeat turns out to be one of the most richly structured floors imaginable.