<p>An extended comment: a recent paper by Demaine &amp; al. proves that one tile is enough to simulate an arbitrary computation:</p>

<p>Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; <a href="http://arxiv.org/abs/1212.4756">One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece</a> (2012)</p>

<p><strong>but</strong> the tiling is not an exact tiling : <em>"... The output one-tile system requires tiles to live on the same square or hexagonal lattice, allows tiles to rotate, and is <strong>nearly plane</strong> tiling in the sense that it leaves tiny gaps between the tiles. ..."</em></p>

CC BY-SA 3.0
2015-09-15T15:33:27.757Z
Nice, that is the fastest answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-09-15T15:48:11.510Z
@MohammadAl-Turkistany: Some time ago, I gave a quick look at the paper but I forgot that the tiling is not exact ... I modified the answer ... :-)
Marzio De Biasi
CC BY-SA 3.0
2015-09-15T15:31:11.157Z
2015-09-15T15:45:30.457Z
2015-09-15T15:45:30.457Z
Marzio De Biasi
<p>According to the introduction of [1],</p>

<ul>
<li>The complexity of determining if a single polyomino tiles the plane remains open [2,3], and</li>
<li>There is an undecidability proof for sets of 5 polyominoes [4].</li>
</ul>

<p>[1] Stefan Langerman, Andrew Winslow. <a href="http://arxiv.org/abs/1507.02762">A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino</a>. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG]</p>

<p>[2] C. Goodman-Strauss. <a href="http://comp.uark.edu/~strauss/papers/survey.pdf">Open questions in tiling</a>. Online, published 2000.</p>

<p>[3] C. Goodman-Strauss. <a href="http://www.ams.org/notices/201003/rtx100300343p.pdf">Can’t decide? undecide!</a> Notices of the American
Mathematical Society, 57(3):343–356, 2010.</p>

<p>[4] N. Ollinger. <a href="https://hal.archives-ouvertes.fr/hal-00335781/document">Tiling the plane with a fixed number of polyominoes</a>. In
A. H. Dediu, A. M. Ionescu, and C. Mart´ın-Vide, editors, LATA 2009,
volume 5457 of LNCS, pages 638–647. Springer, 2009.</p>

CC BY-SA 3.0
2015-09-15T17:41:06.363Z
2015-09-15T18:04:29.430Z
2015-09-15T18:04:29.430Z
Mangara
<p>I know that it is undecidable to determine if a set of tiles can tile the plane,
a result of Berger using <a href="https://en.wikipedia.org/wiki/Wang_tile">Wang tiles</a>.
My question is whether it is also known to be undecidable to determine
if a <em>single</em> given tile can tile the plane, a <em>monohedral</em> tiling.</p>

<p>If this remains unsettled, I would be interested to know what is the minimum
cardinality of a set of tiles for which there is an undecidability proof.
(I have not yet accessed Berger's proof.)</p>

CC BY-SA 3.0
2015-09-15T16:50:20.163Z
Another recent undecidability proof can be found in: Nicolas Ollinger; [Two-by-two Substitution Systems and the Undecidability of the Domino Problem](http://link.springer.com/chapter/10.1007/978-3-540-69407-6_51); Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008 ([pdf](https://hal.inria.fr/file/index/docid/260112/filename/sutica.pdf)) ... but they use more tiles (104) to build an aperiodic tileset (Robinson's proof uses 56 tiles)
Marzio De Biasi
<reference-request><co.combinatorics><decidability><undecidability>
Is it decidable to determine if a given shape can tile the plane?
Joseph O'Rourke
# Is it decidable to determine if a given shape can tile the plane?

(Asked by: username_0 on 2015-09-15)

I know that it is undecidable to determine if a set of tiles can tile the plane,
a result of Berger using [Wang tiles](https://en.wikipedia.org/wiki/Wang_tile).
My question is whether it is also known to be undecidable to determine
if a *single* given tile can tile the plane, a *monohedral* tiling.

If this remains unsettled, I would be interested to know what is the minimum
cardinality of a set of tiles for which there is an undecidability proof.
(I have not yet accessed Berger's proof.)

**Tags:** reference-request, co.combinatorics, decidability, undecidability
> **Comments:**
> **username_1**: Another recent undecidability proof can be found in: Nicolas Ollinger; [Two-by-two Substitution Systems and the Undecidability of the Domino Problem](http://link.springer.com/chapter/10.1007/978-3-540-69407-6_51); Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008 ([pdf](https://hal.inria.fr/file/index/docid/260112/filename/sutica.pdf)) ... but they use more tiles (104) to build an aperiodic tileset (Robinson's proof uses 56 tiles)  

---

## 2 answers

### Answer by username_3 on 2015-09-15. Score: 23 | Accepted answer

According to the introduction of [1],

* The complexity of determining if a single polyomino tiles the plane remains open [2,3], and
* There is an undecidability proof for sets of 5 polyominoes [4].

[1] Stefan Langerman, Andrew Winslow. [A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino](http://arxiv.org/abs/1507.02762). ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG]

[2] C. Goodman-Strauss. [Open questions in tiling](http://comp.uark.edu/~strauss/papers/survey.pdf). Online, published 2000.

[3] C. Goodman-Strauss. [Can’t decide? undecide!](http://www.ams.org/notices/201003/rtx100300343p.pdf) Notices of the American
Mathematical Society, 57(3):343–356, 2010.

[4] N. Ollinger. [Tiling the plane with a fixed number of polyominoes](https://hal.archives-ouvertes.fr/hal-00335781/document). In
A. H. Dediu, A. M. Ionescu, and C. Mart´ın-Vide, editors, LATA 2009,
volume 5457 of LNCS, pages 638–647. Springer, 2009.


---

### Answer by username_1 on 2015-09-15. Score: 14

An extended comment: a recent paper by Demaine & al. proves that one tile is enough to simulate an arbitrary computation:

Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; [One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece](http://arxiv.org/abs/1212.4756) (2012)

**but** the tiling is not an exact tiling : *"... The output one-tile system requires tiles to live on the same square or hexagonal lattice, allows tiles to rotate, and is **nearly plane** tiling in the sense that it leaves tiny gaps between the tiles. ..."*

> **Comments:**
> **username_2**: Nice, that is the fastest answer.  
> **username_1**: @MohammadAl-Turkistany: Some time ago, I gave a quick look at the paper but I forgot that the tiling is not exact ... I modified the answer ... :-)  

---

