Two Tiling is Undecidable

summary

The gist

We show that given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them is undecidable The paper demonstrates that tiling problems involving…

In short

The paper proves that determining if a plane can be tiled by two polygonal prototiles using rotations and translations is undecidable. This result extends previous work on three tiles and establishes undecidability for monotiling with edge-to-edge matching rules. The proof involves reducing the problem to an intermediate, known undecidable problem called AB tiling.

Key concepts

Undecidability for Monotiling
This concept refers to the impossibility of creating an algorithm that can always decide if a single shape (prototile) can tile a plane when strict edge-to-edge matching rules are enforced. The paper shows this is true, even with only local matching rules, which is a significant finding.
AB Tiling Simulation
The authors create an intermediate problem called AB tiling that is known to be undecidable via reduction from Wang tiling. They construct sets of A and B tiles that correspond to Wang tiles, requiring every tile in the geometric tiling to belong to an S-tetromino, linking the two problems together.
Weave Pattern
A weave pattern is a specific structural requirement for tilings involving stick tiles under certain edge-to-edge matching rules. The paper proves that any tiling satisfying these rules must conform to this pattern, which helps characterize the necessary conditions for tiling.

Terminology used across episodes

This episode discusses

The paper

Two Tiling is Undecidable · Read on arXiv

Jack Stade

We show that the following problem is undecidable: given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them. This improves a result of Demaine and Langerman [SoCG 2025], who showed undecidability for three tiles. Along the way, we show that tiling with one prototile is undecidable if there can be edge-to-edge matching rules. This is the first result to show undecidability for monotiling with only local matching constraints.

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Two Tiling is Undecidable".

Jane: Here's the gist of the paper. We show that given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them is undecidable The paper demonstrates that tiling problems involving two polygonal prototiles are undecidable, which improves a previous result concerning three tiles Undecidability for Monotiling with Constraints The paper establishes the undecidability of monotiling when certain additional constraints are enforced, specifically edge-to-edge matching rules Theorem 2 states that there is no algorithm to decide whether a single prototile with edge-to-edge matching rules tiles the plane This result is significant because it shows undecidability for monotiling with only local matching rules, which is a new finding.

Tom: Construction via Weave Patterns The authors prove Theorem 2 by first showing that tiling with a stick tile forms a "weave pattern" under specific edge-to-edge matching rules The weave pattern is defined by several structural requirements concerning the orientation and stacking of sticks.

Jane: Lemma 4 confirms that any tiling satisfying these rules must form a weave pattern.

Tom: Simulation of Wang Tiling via AB Tiles To prove Theorem 1, the authors introduce an intermediate problem called "AB tiling," which is shown to be undecidable by reduction from Wang tiling The construction involves creating sets of A and B tiles that correspond to Wang tiles, where every tile must be part of an S-tetromino.

Paper summary: Jane: So, wrapping up the "Two Tiling is Undecidable" paper by Stade and Stade, what does this mean for tiling theory in general? It improves upon earlier work about three tiles.

Tom: They show that determining whether a plane can be tiled with just two polygonal prototiles using rotations and translations is undecidable. That’s the main takeaway from the paper.

Lu: The implication is that we can't expect a general algorithm to solve tiling problems for two arbitrary tiles, even when we restrict ourselves to certain matching rules like edge-to-edge constraints. It extends the complexity boundary beyond what was previously known for three tiles <ref:2506.11628#pg2>.

Meng: From an engineering standpoint, this means that if you're designing a system where tiling is a constraint, and those constraints involve two specific shapes, you can't rely on an automated checker to give you a definitive yes or no answer for all possible inputs. It puts hard limits on the kind of verification we can build into our software.

Jane: The paper does show how this undecidability arises by reducing it from Wang tiling and using geometric simulations with modified stick tiles and staple tiles <ref:2506.11628#pg3>. So, the underlying mechanism connects known hard problems to this new two-tile scenario.

Tom: It shows that simulating complex matching rules can be done geometrically, which is important because it means we can model those constraints using physical shapes rather than just abstract color schemes. The paper's method for encoding states and gap conditions seems to be the mechanism that makes this reduction work so tightly <ref:2506.11628#pg1>.

Lu: The paper suggests that this technique, using the weave pattern structure and those intricate state machine encodings, can actually be generalized to improve bounds for related tiling problems, like translational three tiles <ref:2506.11628#pg3>. So it's not just a single result; it opens a path for more work.

Meng: If they can generalize this idea, could that lead to something useful in practical AI systems where we need to verify geometric arrangements? For example, if we were verifying the layout of certain tile-based structures?

Jane: That's a big question. The paper itself notes that the method used for encoding states and gap conditions is quite intricate <ref:2506.11628#pg1>. So while it proves undecidability, they don't give us an immediate practical algorithm to solve the tiling problem itself.

Tom: Right, so we have a proven barrier in decidability for two tiles under these rules, but that barrier comes from showing an equivalence to a known hard problem like Wang tiling. That's the main point of "Two Tiling is Undecidable."

Conclusion: Jane: So, to wrap up, the paper shows that deciding if two polygonal prototiles can tile a plane is impossible for an algorithm to solve <ref:2506.11628#pg4>.

Tom: Yeah, they proved it using Wang tiling as a starting point and then building this geometric simulation with modified stick tiles and staple tiles <ref:2506.11628#pg3>.

Lu: The core idea is that you can encode complex matching rules through these state machines and gap conditions, which eventually reduces the problem to an undecidable one.

Meng: So what does this actually mean for us on the ground? It means if you're designing a system where two shapes need to fit together perfectly with specific rules, you can't build a tool that guarantees it will always work for any shape combination.

Jane: Exactly. It shows the limits of automated verification when dealing with these kinds of geometric constraints.

Tom: The authors, Stade and Stade, they showed this by proving that even simple edge-to-edge matching rules are enough to make tiling undecidable <ref:2506.11628#pg2>.

Lu: And the future work they suggest is pretty interesting because it hints that this technique for encoding states could be generalized to improve bounds for things like translational three tile tiling <ref:2506.11628#pg3>.

Meng: If they can really push that generalization, it might mean we get better ways to handle those complex geometric constraints in real-world AI deployment.

Jane: That's what I think. It moves the discussion from just proving something is impossible to figuring out how we can approach problems that are fundamentally hard this way.

More episodes

← Home