Ist es entscheidend zu bestimmen, ob eine gegebene Form die Ebene kacheln kann?

24

Ich weiß, dass es nicht zu entscheiden ist, ob ein Kachelsatz das Flugzeug kacheln kann, ein Ergebnis der Verwendung von Wang-Kacheln durch Berger . Meine Frage ist, ob es auch bekannt ist, unentscheidbar zu sein, um festzustellen, ob eine einzelne gegebene Fliese die Ebene, eine einflächige Kachelung , kacheln kann .

Wenn dies weiterhin ungeklärt bleibt, würde ich gerne wissen, wie hoch die Mindestkardinalität eines Kachelsatzes ist, für den es einen Unentscheidbarkeitsbeweis gibt. (Ich habe noch nicht auf Bergers Beweis zugegriffen.)

Joseph O'Rourke
quelle
Ein weiterer neuer Unentscheidbarkeitsbeweis ist zu finden in: Nicolas Ollinger; Zwei-mal-zwei-Substitutionssysteme und die Unentscheidbarkeit des Domino-Problems ; Logik und Theorie der Algorithmen, 4. Konferenz über Berechenbarkeit in Europa, CiE 2008 ( pdf ) ... aber sie verwenden mehr Kacheln (104), um ein aperiodisches Kachelset zu erstellen (Robinsons Beweis verwendet 56 Kacheln)
Marzio De Biasi

Antworten:

23

Nach der Einführung von [1],

  • Die Komplexität der Bestimmung, ob ein einziges Polyomino die Ebene verfliest, bleibt offen [2,3]
  • Es gibt einen Unentscheidbarkeitsbeweis für Sätze von 5 Polyominoen [4].

[1] Stefan Langerman, Andrew Winslow. Ein quasilinearer Zeitalgorithmus zum isoedrischen Kacheln der Ebene mit einem Polyomino . ArXiv e-prints, 2015. arXiv: 1507.02762 [cs.CG]

[2] C. Goodman-Strauss. Offene Fragen in Kacheln . Online, veröffentlicht 2000.

[3] C. Goodman-Strauss. Sie können sich nicht entscheiden? unentschieden! Mitteilungen der American Mathematical Society, 57 (3): 343–356, 2010.

[4] N. Ollinger. Kacheln des Flugzeugs mit einer festen Anzahl von Polyominoen . In AH Dediu, AM Ionescu und C. Mart´ın-Vide, Herausgeber, LATA 2009, Band 5457 von LNCS, Seiten 638–647. Springer, 2009.

Mangara
quelle
14

Ein erweiterter Kommentar: Ein kürzlich veröffentlichter Artikel von Demaine & al. beweist, dass eine Kachel ausreicht, um eine beliebige Berechnung zu simulieren:

Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; Eine Kachel für alle: Simulation einer beliebigen Turingmaschine, eines Fliesenmontagesystems oder eines Kachelsystems mit einem einzigen Puzzleteil (2012)

aber die Fliesen sind keine exakten Fliesen: “... Die Ausgabe eines Plattensystem Fliesen erfordert auf dem gleichen Platz oder hexagonale Gitter zu leben, kann Fliesen zu drehen, und ist fast ebene Kacheln in dem Sinne , dass es winzige Lücken läßt zwischen die Fliesen. ... "

Marzio De Biasi
quelle
Schön, das ist die schnellste Antwort.
Mohammad Al-Turkistany,
@ MohammadAl-Turkistany: Vor einiger Zeit habe ich einen kurzen Blick auf die Zeitung geworfen, aber ich habe vergessen, dass die Kacheln nicht genau sind ... Ich habe die Antwort geändert ... :-)
Marzio De Biasi