Wiem, że nierozstrzygalne jest ustalenie, czy zestaw kafelków może kafelkować płaszczyznę, w wyniku Bergera korzystającego z kafelków Wanga . Moje pytanie brzmi: czy wiadomo również, że nierozstrzygalne jest ustalenie, czy pojedyncza dana płytka może ułożyć płytkę, monoedryczną płytkę.
Jeśli to pozostanie nierozwiązane, chciałbym wiedzieć, jaka jest minimalna liczność zbioru płytek, dla których istnieje dowód nierozstrzygalności. (Nie uzyskałem jeszcze dostępu do dowodu Bergera).
reference-request
co.combinatorics
decidability
undecidability
Joseph O'Rourke
źródło
źródło
Odpowiedzi:
Zgodnie z wprowadzeniem [1]
[1] Stefan Langerman, Andrew Winslow. Algorytm czasowy quasilinear dla izowrotrycznego układania płaszczyzny za pomocą Polyomino . E-wydruki ArXiv, 2015. arXiv: 1507.02762 [cs.CG]
[2] C. Goodman-Strauss. Otwarte pytania w kafelkach . Online, opublikowany 2000.
[3] C. Goodman-Strauss. Nie możesz się zdecydować? niezdecydować! Notices of the American Mathematical Society, 57 (3): 343–356, 2010.
[4] N. Ollinger. Układanie płaszczyzny za pomocą stałej liczby poliominoes . W AH Dediu, AM Ionescu i C. Mart´ın-Vide, redaktorzy, LATA 2009, tom 5457 LNCS, strony 638–647. Springer, 2009.
źródło
Rozszerzony komentarz: najnowszy artykuł Demaine i in. dowodzi, że jeden kafelek wystarcza do symulacji dowolnego obliczenia:
Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; Jeden kafelek, aby rządzić nimi wszystkimi: Symulacja dowolnej maszyny Turinga, systemu składania kafelków lub systemu kafelkowego za pomocą pojedynczego elementu układanki (2012)
ale kafelki nie są dokładnymi kafelkami: „... Wyjściowy system z jednym kafelkiem wymaga, aby kafelki żyły na tej samej kwadratowej lub sześciokątnej kratce, pozwala na obracanie kafelków i jest prawie płaskie kafelkowanie w tym sensie, że pozostawia niewielkie odstępy między płytki. ”
źródło