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.)
reference-request
co.combinatorics
decidability
undecidability
Joseph O'Rourke
quelle
quelle
Antworten:
Nach der Einführung von [1],
[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.
quelle
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. ... "
quelle