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).
reference-request
co.combinatorics
decidability
undecidability
Joseph O'Rourke
fuente
fuente
Respuestas:
Según la introducción de [1],
[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.
fuente
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. ..."
fuente