É decidível determinar se uma determinada forma pode ladrilhar o avião?

24

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

Joseph O'Rourke
fonte
Outra prova recente de indecidibilidade pode ser encontrada em: Nicolas Ollinger; Sistemas de substituição de dois por dois e a indecidibilidade do problema do dominó ; Lógica e Teoria de Algoritmos, 4ª Conferência sobre Computability na Europa, CIE 2008 ( pdf ) ... mas eles usam mais peças (104) para construir um tileset aperiodic (usos prova de Robinson 56 telhas)
Marzio De Biasi

Respostas:

23

De acordo com a introdução de [1],

  • A complexidade de determinar se um único poliomino ladrilha o avião permanece aberto [2,3], e
  • Existe uma prova de indecidibilidade para conjuntos de 5 poliaminoinos [4].

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

Mangara
fonte
14

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

Marzio De Biasi
fonte
Bom, essa é a resposta mais rápida.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Algum tempo atrás, eu dei uma olhada rápida no papel, mas eu esqueci que o piso não é exato ... eu modifiquei a resposta ... :-)
Marzio De Biasi