¿Vista de un polytope de dimension $n$, hay alguna manera general para determinar si puede azulejo $\mathbb{R}^n$?
Respuestas
¿Demasiados anuncios?
Oli
Puntos
89
guruz
Puntos
1129
Editar 9/30/2015 Mi revisado comprensión todavía no es correcta! El undecidability del mosaico problema no es equivalente a la existencia de una aperiódica suelo de baldosas. Ver Edmund Harris respuesta en este relacionado MO post.
Editar 3/14/2013: Mi respuesta original a continuación fue confuso "undecidability" con "independencia de los axiomas de la teoría de conjuntos," y quiero comenzar con mi revisado, esperemos que la comprensión más precisa.
En un momento en el tiempo, que estaba abierto sobre si existe o no una máquina de Turing que podría decidir si un determinado conjunto de azulejos sería azulejo el avión. A continuación, Hao Wang mostró que este problema se ha hecho decidable si y sólo si cada conjunto de mosaicos que podría azulejo el avión podría hacerlo periódicamente. Wang estudiante de Berger, y más tarde otros como Penrose demostraron la existencia de aperiódica juegos de fichas, lo que demuestra a través de Wang resultado que el suelo de baldosas problema es indecidible. (No máquina de Turing era capaz de escupir un sí-sin respuesta, dado un conjunto de baldosas.) Durante mucho tiempo se mantuvo abierto si había un solo azulejo que sólo podía azulejo aperiodically. (Penrose había llegado a 2. Berger había comenzado con cerca de 20.000 creo.) Pero luego en el 2010 Taylor-Socolar azulejo fue descubierto. Se trata de una sola desconectado de baldosas de que los azulejos de los planos, pero sólo aperiodically. He incluido una foto.
Esto no directamente a la dirección de la OP, pero es sugerente que podría ser un problema indecidible.
Post Original: Probablemente no hay! De hecho, creo que hay una sola (muy complicado) 2D azulejo para el que el problema de si las baldosas del avión que lógicamente es indecidible [Editar: significado independiente de los axiomas de la teoría de conjuntos ZFC]! No tengo la referencia a mano. Tal vez alguien más puede ofrecer. Con una rápida búsqueda en Google, el artículo de la Wikipedia sobre Wang azulejos es lo más cercano que podría venir. Wang azulejos se presentan como azulejos de colores donde los colores para que coincidan con los bordes compartidos, pero estos pueden ser convertidos a regular las baldosas mediante la modificación de los límites, de modo que sólo los colores pueden unirse. De acuerdo a Wikipedia, no es un conjunto de 13 de baldosas para que el mosaico problema es lógicamente indecidible [Editar: significado independiente de los axiomas de la teoría de conjuntos ZFC], pero me parece recordar audiencia que este número se ha reducido a 1, pero posiblemente ya no hay en el Wang azulejo de la categoría.
Edit: Como me fue apuntado en los comentarios, este parece ser diferente a preguntar si el mosaico problema es decidable en la decisión problema de sentido, para que la verdad de cualquier finito proposición se supone que se conocen, y la pregunta es si existe un algoritmo que se ejecuta con éxito en el conjunto de todos los azulejos.
