Sei que é indecidível determinar se um conjunto de peças pode ladrilhar o avião, resultado de Berger usar as peças Wang . Minha pergunta é se é também conhecido como indecidível determinar se um único bloco pode ladrilhar o avião, um bloco monohédico .
Se isso não for resolvido, eu estaria interessado em saber qual é a cardinalidade mínima de um conjunto de peças para as quais existe uma prova de indecidibilidade. (Ainda não acessei a prova de Berger.)
reference-request
co.combinatorics
decidability
undecidability
Joseph O'Rourke
fonte
fonte
Respostas:
De acordo com a introdução de [1],
[1] Stefan Langerman, Andrew Winslow. Algoritmo de tempo quaseilinear para ladrilhar o plano isoédricamente com um poliomino . Impressões eletrônicas ArXiv, 2015. arXiv: 1507.02762 [cs.CG]
[2] C. Goodman-Strauss. Perguntas abertas em ladrilhos . Online, publicado em 2000.
[3] C. Goodman-Strauss. Não pode decidir? indeciso! Avisos da Sociedade Americana de Matemática, 57 (3): 343–356, 2010.
N. Ollinger. Colocando o avião em mosaico com um número fixo de poliaminoinos . Em AH Dediu, AM Ionescu e C. Mart´ın-Vide, editores, LATA 2009, volume 5457 do LNCS, páginas 638-647. Springer, 2009.
fonte
Um comentário estendido: um artigo recente de Demaine & al. prova que um bloco é suficiente para simular uma computação arbitrária:
Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; Um lado a lado para governar todos: simulação de qualquer máquina de Turing, sistema de montagem de lado a lado ou sistema de lado a lado com uma única peça de quebra-cabeça (2012)
mas o ladrilho não é exatamente o ladrilho exato: "... O sistema de saída de um ladrilho exige que os ladrilhos morem na mesma estrutura quadrada ou hexagonal, permite que os ladrilhos girem e é quase ladrilhado no sentido de deixar pequenas lacunas entre os azulejos. "
fonte