Gliders on Aperiodic Monotilings: Cellular Automata on the Hat and Spectre

summary

The gist

Gliders on Aperiodic Monotilings: Cellular Automata on the Hat and Spectre asks whether these monotilings support gliders…

In short

Researchers investigated whether cellular automata on aperiodic Hat and Spectre tilings support gliders, patterns that travel indefinitely. Using evolutionary search and rule extensions, they discovered gliders on both monotilings, traveling one million rings at constant speed. This suggests that orientational order in the tiling's graph metric is sufficient to steer mobile objects.

Key concepts

Aperiodic Monotiles
These are single shapes that can tile a plane but never repeat their pattern through simple translation. The Hat and Spectre tilings were used as complex substrates to test if dynamic patterns like gliders could exist on them, challenging the idea that periodicity is required for tiling.
Cellular Automata (CA)
A system where the state of each cell in a grid changes based on its current state and the states of its neighbors. The experiment uses these rules to see if complex, long-lasting patterns like gliders can emerge from simple local interactions on the tiling.
Gliders
These are bounded patterns within a CA that travel indefinitely across the substrate without changing their shape or speed. Finding them on aperiodic tilings is significant because it suggests that directed transport doesn't strictly require periodic structure.
Graph Metric and Compass Law
The tiling has an underlying geometric structure represented by a graph metric, which defines specific directions (six spokes). The movement of the discovered gliders is quantized to these directions, showing that their travel is dictated by the inherent orientational order of the tiling itself.

Terminology used across episodes

This episode discusses

The paper

Gliders on Aperiodic Monotilings: Cellular Automata on the Hat and Spectre · Read on arXiv

James Edmond

Transcript

Introduction to the show: ident: Nonlinear Sciences. The day in nonlinear science: chaos, patterns, networks and adaptation.

Kai: I'm Kai.

Mira: And I'm Mira, here with Lev.

Kai: We're looking at the paper: "Gliders on Aperiodic Monotilings".

Mira: Here's the gist of the paper. Gliders on Aperiodic Monotilings: Cellular Automata on the Hat and Spectre asks whether these monotilings support gliders, bounded patterns that travel indefinitely The paper investigates whether the hat and spectre tilings support gliders, bounded patterns that travel indefinitely The Nature of Aperiodic Dynamics Aperiodic monotiles are single shapes whose copies tile the plane but never periodically The existence of such a shape remained open for over half a century until 2023, with the hat tiling and spectre tiling being studied as substrates for dynamics This paper asks whether the monotilings support gliders, bounded patterns that travel indefinitely An aperiodic tiling revokes exactly this guarantee because no translation maps the tiling to itself The experiment is organized around how such a claim can be tested, where every experiment is a compact record from which patch and run regenerate deterministically via the substitution-transducer machinery of Tatham Classification is exact, with periods detected as exact recurrences of the full patch state Verification requires cross-radius verification, meaning the candidate must reach the boundary at every radius in a geometric family with a flat peak population at every scale Search Space and Rule Families The rule families used are semi-totalistic because variable neighborhood sizes force transitions to depend on the number of neighbors in given states but not their arrangement Two families are employed: the Generations family, which defines dying phases that age deterministically toward death, and priority-table rules, which allow non-quiescent states other than 1 to be visible to neighbors under conjunctive conditions Searches are conducted using a genetic algorithm where the fitness function is defined by a ratio of growth-slope probe Key Findings on Glider Discovery The evolutionary search discovers gliders on both monotilings, tracked by a sliding window that regenerates the patch along the flight The paper reports findings across four key contributions, including a reproduction of the published Penrose glider with a corrected transition table and blind rediscovery of gliders on that tiling Gliders on both the hat and the spectre are found, traveling one million rings at constant speed and heading in a sliding window Every mobile object travels along directions quantized to its substrate’s orientational order, with every one agreeing with a single per-substrate offset Substrate Geometry and Compass Law The compass law is measured exactly, showing that every mobile object travels on a fan of directions quantized to 60◦ On the monotilings all six spokes carry measured lanes, and the fan directions are the cusp axes of the tiling’s graph metric The compass phase is a constant of the tiling, not of the rule Ablation and Structural Controls An ablation shows that both rule-space extensions—the vertex neighborhood and neighbor-visible states with conjunctive conditions—are each individually necessary The search discovered boundary sniffing on edge-adjacency patches, a parasite that is excluded by a causality filter, suggesting that every objective breeds its parasite and every parasite must become a structural control The contrast between the Penrose gliders and the monotile gliders localizes what directed transport actually requires The substrates share not rails but orientational order, which evidently suffices to steer a relay Future work is led by the certificate problem: can verified to a million rings be upgraded to immortal on every legal tiling The observed repertoire is nonetheless a real starting kit for engineering, suggesting that multi-glider configurations have a discrete, enumerable set of stable geometries Reproducibility Everything reported here regenerates from a small artifact set, including the engine and every committed result record The companion interactive essay presents the same records live at offlattice.org/monotile/essay/, where every panel replays a committed record Three determinism properties underwrite the scheme, ensuring that patches regenerate exactly from their identifiers and searches are deterministic given their recorded parameters and seeds The repository is public at github.com/jamesedmond/monotile-ca and archived at Zenodo (doi:10.5281/zenodo.

Paper summary: Kai: So we’re looking at this paper "Gliders on Aperiodic Monotilings: Cellular Automata on the Hat and Spectre". The main idea is testing whether these specific aperiodic tilings, the hat and spectre monotiles discovered in twenty twenty three, can actually support gliders, which are those bounded patterns that travel around indefinitely.

Mira: It seems like they’re asking if these tilings support gliders because no translation maps the tiling onto itself, so any pattern that survives must be somehow special > I mean aperiodic tilings inherently revoke the guarantee of periodicity > That means you can't have those rails you see in some other tiling structures > It’s a big question about what directed transport even looks like on these substrates.

Lev: From an engineering standpoint, the whole setup is that every experiment is just a small record, and from that record you can deterministically regenerate the patch and the run using substitution-transducer machinery of Tatham twelve > That means if you have a seed and a rule set, you can replay exactly what happened > We need to know how much overhead this deterministic regeneration adds to running these searches on real hardware <ref:2609.22579#pg3,substitution-transducer machinery of Tatham 12>.

Kai: Exactly, it’s about that determinism, and they start by looking at edge-adjacency semi-totalistic rules where they find only mortal travelers and gliders are absent > Then they extend the rule space to include vertex neighborhoods and priority-table rules where non-quiescent states are visible to neighbors > That’s a key part of their methodology.

Mira: And that extension is necessary because the initial simple search didn't find anything, so you have to add complexity to the search space > They then use an evolutionary search with a fitness function based on growth-slope probe > It seems they need those richer rule families just to find anything interesting.

Lev: If we take those priority-table rules, it means the non-quiescent states are visible under conjunctive conditions, which adds a lot of constraints to what the automaton can do > That’s where things get computationally heavy; you're looking at complex state dependencies.

Paper summary: Kai: And they found gliders on both monotilings using this extended rule space > They track these gliders with a sliding window that regenerates the patch along the flight, and they travel one million rings at constant speed and heading > That’s a big number for sustained motion on such complex structures.

Mira: one million rings is significant because it shows sustained travel, but they also quantify the heading by mapping it onto a six-spoke compass using millidegrees > That means the direction isn't arbitrary; it’s tied to the fast axes of the tiling’s graph metric > It links movement directly to the structure itself.

Lev: Quantizing those headings to millidegrees onto that six-spoke compass is a specific constraint, and they say all headings are quantized, which is good for simulation but introduces discretization error > We have to ask if that quantization fundamentally limits the kinds of motion we can actually observe on real systems.

Kai: An ablation shows that both rule-space extensions—the vertex neighborhood and neighbor-visible states with conjunctive conditions—are individually necessary > They also found boundary sniffing on edge-adjacency patches, but they filter that out because it’s a parasite excluded by a causality filter > It suggests every objective breeds its own parasite and every parasite needs to be controlled.

Mira: That’s a strong statement about the structural controls, implying that just having the objective isn't enough; you need these specific structural constraints to stabilize the dynamics > It means the geometry of the tiling imposes requirements on how a rule set must be configured for something like this to happen.

Lev: If we were trying to build hardware for this, it would mean our error correction codes would have to account for these complex, non-local state dependencies imposed by those priority-table rules > The overhead lands in tracking all those neighbor states and the conditional logic.

Kai: And the results replay exactly in an accompanying interactive essay, which is really cool because you can see every single step of the experiment from a small record > It makes it verifiable, which is hard for these kinds of complex systems to do on their own.

Paper summary: Mira: So we’re seeing that directed transport doesn't necessarily require those straight rails found in tilings like Penrose > The paper suggests the substrate provides orientational order instead > It’s not about having rails; it’s about the six-spoke compass directions being dictated by the tiling's graph metric.

Lev: That implies that the fundamental requirement for gliders might just be this specific type of long-range orientational order, rather than a specific lattice structure > We need to see if that order is robust across different tiling families.

Kai: The contrast between the Penrose gliders and these monotile gliders localizes what directed transport actually requires > It suggests that the substrates share not rails but just this orientational order, which evidently suffices to steer a relay.

Mira: So for someone listening who isn't deep in cellular automata, it means you don't need a perfect grid with straight paths to get sustained, directed movement > You just need the local geometry to have this specific rotational symmetry that dictates where the glider can go next.

Lev: The paper also points toward future work regarding the certificate problem, asking if verified travel to a million rings could be upgraded to immortal on every legal tiling > That’s a huge leap from finite simulation to something truly stable.

Kai: So, what does this mean for us looking at quantum hardware? It suggests that even in complex systems we build with qubits, the underlying geometry or substrate might dictate fundamental constraints on how patterns can evolve and travel > We are essentially looking for the "orientational order" equivalent in our physical systems.

Mira: It means we should stop just looking at periodicity and start asking about how local connectivity enforces global structure in aperiodic settings > The assumption that aperiodicity kills directed motion might be too strong if you include these sophisticated local rules.

Lev: From an error correction view, the fact that they found this behavior on these specific patches means we have a new kind of pattern we need to account for when designing fault-tolerant systems > It’s not just about finding errors; it’s about understanding the geometry that allows patterns to persist against them.

Conclusion: Kai: So we've seen how they found gliders on these hat and spectre tilings, and now we’re getting to the conclusion about what this actually means for tiling dynamics.

Mira: It's interesting how they focused on these two specific shapes, the hat and the spectre, because it really zeroes in on whether aperiodicity itself stops directed motion entirely.

Lev: From my side as an error-correction guy, if these patterns are truly stable over a million rings with that kind of local rule complexity, we have to think about how robust those state transitions are under real-world noise.

Kai: Right, so the paper is basically asking if you can actually get sustained travel on a tiling that never repeats itself.

Mira: They found gliders because the substrate provides an orientational order—that six-spoke compass law—which steers the glider one million rings at constant speed and heading.

Lev: That compass direction isn't arbitrary; it’s tied to the fast axes of the tiling’s graph metric, which is a very specific geometric constraint on how that automaton moves.

Kai: It seems like they found that you don't need those straight rails you see in other tilings, but rather this kind of rotational symmetry to get sustained transport.

Mira: That's what it implies about the world of these systems; the substrate isn't just a flat grid with fixed paths, it’s about how local connectivity enforces global structure in a way that steers movement.

Lev: It changes how we think about building things on these surfaces because you aren't just looking for periodicity anymore; you’re looking for this specific order.

Kai: So the big question is whether verified travel to a million rings could actually be upgraded to something immortal on every legal tiling, which is the certificate problem they mention.

Mira: That certificate problem is huge; it asks if we can prove that a pattern will stay stable forever across any valid tiling structure we find.

Lev: If that proof works out, it means the engineering overhead for error correction would change because you'd be tracking these complex, non-local state dependencies in real-time.

Kai: We've seen the mechanics of the discovery; now we have to consider what this suggests for building things with qubits where the underlying geometry dictates constraints on how patterns can evolve.

More episodes

← Home