Two Tiling is Undecidable

arXiv:2506.11628 · cs.CG, math.CO, math.MG · Submitted 2025-06-13 · Read on arXiv

Listen

Radio episode about this paper

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.

Jack Stade

cs.CG, math.CO, math.MG

Submitted: 2025-06-13

Updated: 2026-11-13

Comments: 38 pages, 48 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

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…

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

Summary

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.

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. Lemma 4 confirms that any tiling satisfying these rules must form a weave pattern. p. 4

Where the paper says it

Note that none of the forbidden cases occur in a weave pattern. Any tiling of the plane by a stick of length at least 5 that satisfies the rules 1 through 11 must form a weave pattern.

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. This reduction allows them to show that geometric tiling with two prototiles is undecidable. p. 1

Where the paper says it

We improve this result, showing that geometric tiling is undecidable with 2 prototiles: Theorem 1. There is no algorithm, that, given two polygonal prototiles, decides whether they tile the plane.

Geometric Simulation of Matching Rules

The authors simulate the edge-to-edge matching rules by modifying the edges of the stick tile and adding a second staple tile, which is a regular 12-gon Lemma 7 proves that these modified tiles can tile the plane if and only if the unmodified stick tile respects the matching rules. p. 2

Where the paper says it

There are many different ways to tile the plane with stick tiles. Our first step is to add some edge-to-edge matching rules that restrict the tile to forming a particularly nice type of a tiling that we call a weave pattern.

This simulation technique is used to prove Theorem 3, showing translational 4-tiling is undecidable. p. 1
Where the paper says it

Previously, Yang and Zhang [12] showed that translational 8-tiling is undecidable. Our construction uses only 4 total orientations of our 2 tiles, showing that: Theorem 3.

Final Verification and Generalization

The final verification step shows that if a single prototile tiles the plane, it must form a weave pattern whose schematic satisfies the gap conditions The construction of the AB tiling encoding states and color-matching constraints is detailed to fully characterize valid schematics The paper concludes by showing that this method can be generalized to improve bounds for related tiling problems, such as translational 3-tiling.

Conclusion

The paper proves that deciding whether a single prototile T with edge-to-edge matching rules tiles the plane is undecidable This result is achieved by reducing the problem to an AB tiling problem, which itself is undecidable. The construction successfully simulates complex matching rules using geometric modifications and staple tiles. p. 1

Where the paper says it

Our result is the first to show undecidability for monotiling with only local matching rules. We first prove Theorem 2 in Section 2, and in Section 3 we show how to obtain Theorem 1 by adding a “staple” tile that simulates edge-to-edge matching rules.

The findings have implications for understanding the limits of decidability in tiling problems. p. 1
Where the paper says it

A classic problem asks which tiling problems are decidable, that is, when is there an algorithm that can determine whether a set of prototiles admits a tiling? In 1966, Berger [1] showed that the Wang tiling problem is undecidable.

The paper also suggests that tiling with 3 polyomino prototiles is undecidable under certain conditions. p. 1
Where the paper says it

We make some progress towards answering this question, showing that monotiling is undecidable when certain additional constraints are enforced. An edge-to-edge matching rule is a constraint that prevents certain pairs of edges of prototiles from being placed next to each other in a tiling.

The open problem regarding the decidability of monotiling remains important. p. 1
Where the paper says it

There is no algorithm, that, given two polygonal prototiles, decides whether they tile the plane. A longstanding open problem [5] asks whether monotiling is decidable.

Pruning redundant reasoning tokens

The authors show that tiling with one prototile is undecidable if there can be edgeto-edge matching rules They first prove Theorem 2 in Section 2, and in Section 3 we show how to obtain Theorem 1 by adding a “staple” tile that simulates edge-to-edge matching rules. Both Theorem 1 and Theorem 2 are stated in the setting where rotations are allowed by reflections are prohibited. p. 1

Where the paper says it

This is based on a similar use of a staple tile in [2]. Both Theorem 1 and Theorem 2 are stated in the setting where rotations are allowed by reflections are prohibited.

Where the gains come from

The core of the proof lies in constructing a complex set of constraints through gap conditions derived from schematic representations The construction involves dividing the block into buckets and defining states that cycle through a sequence, where each state dictates how gaps must fit above a specific bucket. This system is then linked to the structure of an AB tiling through encoding states. p. 0

Where the paper says it

5 The gap conditions . 6 Structure of states representing an AB tiling .

How the training signal is built

The coloring constraints are created by splitting the space between encoding states by adding intermediate states like e1.5 and e3.5 These intermediate states enforce color matching rules on opposite sides of edges, which is crucial for simulating Wang tile constraints. p. 0

Where the paper says it

31 3 Simulating matching rules geometrically 32 4 Conclusion 34 5 Acknowledgments 36 1 Introduction A tiling problem (in R 2 ) asks whether a given set prototiles can tile the plane, that is whether there is a tiling of the plane where every tile is a copy of one of the prototiles. Rotations and reflections may or may not be allowed, and there may be some constraints on how tiles can be placed in relation to each other.

p. 0
Where the paper says it

31 3 Simulating matching rules geometrically 32 4 Conclusion 34 5 Acknowledgments 36 1 Introduction A tiling problem (in R 2 ) asks whether a given set prototiles can tile the plane, that is whether there is a tiling of the plane where every tile is a copy of one of the prototiles. Rotations and reflections may or may not be allowed, and there may be some constraints on how tiles can be placed in relation to each other.

The specific values assigned to the left and right lengths of gaps in these states are determined by parameters Li, Ri, and Ii. p. 0
Where the paper says it

3 Tiling schematics . 4 States and buckets .

p. 0
Where the paper says it

3 Tiling schematics . 4 States and buckets .

The construction of the AB pattern involves creating an S-tetromino from the corresponding A and B tiles The correspondence between Wang tiles and AB tiles is established through a reduction where every tile must be part of one of these tetrominoes. This reduction is used to show that tilings with these tetrominos are in correspondence with tilings by the Wang tiles. p. 1

Where the paper says it

In 1966, Berger [1] showed that the Wang tiling problem is undecidable. This is a tiling problem where the prototiles are squares with colored edges, where the tiles should be placed without rotations on a square grid so that colors match along coincident edges.

The simulation of matching rules geometrically relies on constructing modified stick tiles and a regular 12-gon staple tile The modification involves designating specific spots on the edges with bumps or dents based on the matching rules. Lemma 7 proves that these modified tiles can tile the plane if and only if the unmodified stick tile respects the matching rules.

The constraints are formalized through a schematic representation where rows cycle through states, and gaps in a row must fit above a specific bucket in the row below Lemma 9 describes how the values of gaps in one row relate to those in the rows below it, ensuring that adjacent gaps satisfy certain algebraic relationships. This mechanism ensures that if a row is in state i, then the row below it is in state σ(i).

The final verification step shows that if a single prototile tiles the plane, it must form a weave pattern whose schematic satisfies the gap conditions By Lemma 4, this tiling forms a weave pattern The authors then show that the gaps in this schematic satisfy the gap conditions. This assignment can be used to generate a valid schematic, which can be used to construct a weave-pattern tiling with copies of T. p. 2

Where the paper says it

There are many different ways to tile the plane with stick tiles. Our first step is to add some edge-to-edge matching rules that restrict the tile to forming a particularly nice type of a tiling that we call a weave pattern.

The construction of the AB tiling encoding states is highly intricate, involving multiple encoding states (e1 through e4) that represent different parts of an AB tiling structure The specific rules governing transitions between these states, such as those described in Lemma 10 and Lemma 12, are what allow the simulation of the tile placement constraints. This intricate state machine is what ultimately proves that the tiling problem is undecidable. p. 0

Where the paper says it

11628v1 [cs. CG] 13 Jun 2025 Two Tiling is Undecidable Jack Stade February 2025 Abstract 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.

The color-matching constraints are created by splitting the space between encoding states by adding intermediate states like e1.5 and e3.5 These intermediate states enforce color matching rules on opposite sides of edges, which is crucial for simulating Wang tile constraints. The specific values assigned to the left and right lengths of gaps in these states are determined by parameters Li, Ri, and Ii.

The construction of the AB pattern involves creating an S-tetromino from the corresponding A and B tiles The correspondence between Wang tiles and AB tiles is established through a reduction where every tile must be part of one of these tetrominoes This reduction is used to show that tilings with these tetrominos are in correspondence with tilings by the Wang tiles.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved AI systems can determine whether a plane can be tiled with two polygonal prototiles by reducing this problem to simulating edge-to-edge matching rules through an AB tiling construction that is then mapped to a stick tile.

  2. The improved system can decide if a single prototile with edge-to-edge matching rules tiles the plane by constructing an AB tiling where a set of Wang tiles corresponds to the constraints, and then verifying if the resulting schematic satisfies specific gap conditions.

  3. The system can generate a complete schematic for an AB tiling given a set of A and B tiles, which corresponds to a valid stick tiling if and only if the corresponding AB-tiling exists, effectively simulating complex matching rules geometrically.

Abstract

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.

Sources

Related papers