25
$\begingroup$

I know that it is undecidable to determine if a set of tiles can tile the plane, a result of Berger using Wang tiles. 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.)

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
23
$\begingroup$

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. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG]

[2] C. Goodman-Strauss. Open questions in tiling. Online, published 2000.

[3] C. Goodman-Strauss. Can’t decide? undecide! Notices of the American Mathematical Society, 57(3):343–356, 2010.

[4] N. Ollinger. Tiling the plane with a fixed number of polyominoes. In A. H. Dediu, A. M. Ionescu, and C. Mart´ın-Vide, editors, LATA 2009, volume 5457 of LNCS, pages 638–647. Springer, 2009.

Improve this answer
$\endgroup$
14
$\begingroup$

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 (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. ..."

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice, that is the fastest answer. $\endgroup$
    – Mohammad Al-Turkistany
    Sep 15, 2015 at 15:33
  • $\begingroup$ @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 ... :-) $\endgroup$
    – Marzio De Biasi
    Sep 15, 2015 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.