¿Es decidible determinar si una forma dada puede enlosar el plano?

24

Sé que es indecidible determinar si un conjunto de fichas puede enlosar el plano, como resultado de que Berger usa fichas de Wang . Mi pregunta es si también se sabe que es indecidible determinar si un solo mosaico dado puede enlosar el plano, un mosaico monoédrico .

Si esto sigue sin resolverse, me interesaría saber cuál es la cardinalidad mínima de un conjunto de mosaicos para los que existe una prueba de indecidibilidad. (Todavía no he accedido a la prueba de Berger).

Joseph O'Rourke
fuente
Otra prueba reciente de indecidibilidad se puede encontrar en: Nicolas Ollinger; Sistemas de sustitución dos por dos y la indecidibilidad del problema del dominó ; Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008 ( pdf ) ... pero usan más mosaicos (104) para construir un mosaico aperiódico (la prueba de Robinson utiliza 56 mosaicos)
Marzio De Biasi

Respuestas:

23

Según la introducción de [1],

  • La complejidad de determinar si un solo polyomino recubre el plano permanece abierto [2,3]
  • Existe una prueba de indecidibilidad para conjuntos de 5 poliominós [4].

[1] Stefan Langerman, Andrew Winslow. Algoritmo de tiempo cuasilineal para poner en mosaico el plano isoédricamente con un poliomino . Impresiones electrónicas de ArXiv, 2015. arXiv: 1507.02762 [cs.CG]

[2] C. Goodman-Strauss. Preguntas abiertas en mosaico . En línea, publicado en 2000.

[3] C. Goodman-Strauss. No puedo decidir indeciso! Notices of the American Mathematical Society, 57 (3): 343–356, 2010.

[4] N. Ollinger. Alicatar el avión con un número fijo de poliominós . En AH Dediu, AM Ionescu y C. Mart´ın-Vide, editores, LATA 2009, volumen 5457 de LNCS, páginas 638–647. Springer, 2009.

Mangara
fuente
14

Un comentario extendido: un artículo reciente de Demaine & al. demuestra que un mosaico es suficiente para simular un cálculo arbitrario:

Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; Un mosaico para gobernarlos a todos: simulando cualquier máquina de Turing, sistema de ensamblaje de mosaico o sistema de mosaico con una sola pieza de rompecabezas (2012)

pero el mosaico no es un mosaico exacto: "... El sistema de un mosaico de salida requiere que los mosaicos vivan en el mismo enrejado cuadrado o hexagonal, permite que los mosaicos roten y es mosaico casi plano en el sentido de que deja pequeños espacios entre Los azulejos. ..."

Marzio De Biasi
fuente
Bien, esa es la respuesta más rápida.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Hace algún tiempo, eché un vistazo rápido al periódico, pero olvidé que el mosaico no es exacto ... Modifiqué la respuesta ... :-)
Marzio De Biasi