Czy można rozstrzygnąć, czy dany kształt może pokryć płaszczyznę?

24

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).

Joseph O'Rourke
źródło
Kolejny niedawny dowód nierozstrzygalności można znaleźć w: Nicolas Ollinger; Systemy zastępowania dwa na dwa i nierozstrzygalność problemu Domina ; Logika i Teoria algorytmów 4. Konferencji na obliczalności w Europie, CIE 2008 ( pdf ) ... ale używają więcej płytek (104) zbudować aperiodyczny zestaw klocków (dowód zastosowania Robinsona 56 płytek)
Marzio De Biasi

Odpowiedzi:

23

Zgodnie z wprowadzeniem [1]

  • Złożoność określenia, czy pojedyncza płytka poliomino płaszczyzna pozostaje otwarta [2,3], i
  • Istnieje dowód nierozstrzygalności dla zestawów 5 poliominoesów [4].

[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.

Mangara
źródło
14

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. ”

Marzio De Biasi
źródło
Fajnie, to najszybsza odpowiedź.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Jakiś czas temu rzuciłem okiem na papier, ale zapomniałem, że kafelki nie są dokładne ... Zmieniłem odpowiedź ... :-)
Marzio De Biasi