stringtranslate.com

Azulejo Wang

Este conjunto de 11 fichas Wang cubrirá el plano, pero solo de forma aperiódica .

Las fichas de Wang (o fichas de dominó de Wang ), propuestas por primera vez por el matemático, lógico y filósofo Hao Wang en 1961, son una clase de sistemas formales . Se modelan visualmente mediante fichas cuadradas con un color en cada lado. Se selecciona un conjunto de dichas fichas y se colocan copias de las fichas una al lado de la otra con colores coincidentes, sin rotarlas ni reflejarlas.

La cuestión básica sobre un conjunto de teselas de Wang es si puede teselar el plano o no, es decir, si se puede llenar de esta manera un plano infinito entero. La siguiente pregunta es si esto se puede hacer siguiendo un patrón periódico.

Problema del dominó

Ejemplo de teselación Wang con 13 piezas.

En 1961, Wang conjeturó que si un conjunto finito de fichas de Wang puede teselar el plano, entonces también existe un teselado periódico , que, matemáticamente, es un teselado que es invariante bajo traslaciones por vectores en una red bidimensional. Esto se puede comparar con el teselado periódico en un patrón de papel tapiz, donde el patrón general es una repetición de algún patrón más pequeño. También observó que esta conjetura implicaría la existencia de un algoritmo para decidir si un conjunto finito dado de fichas de Wang puede teselar el plano. [1] [2] La idea de restringir las fichas adyacentes para que coincidan entre sí ocurre en el juego de dominó , por lo que las fichas de Wang también se conocen como dominó de Wang. [3] El problema algorítmico de determinar si un conjunto de fichas puede teselar el plano se conoció como el problema del dominó . [4]

Según el estudiante de Wang, Robert Berger , [4]

El problema del dominó se ocupa de la clase de todos los conjuntos de dominó. Consiste en decidir, para cada conjunto de dominó, si es o no solucionable. Decimos que el problema del dominó es decidible o indecidible según exista o no un algoritmo que, dadas las especificaciones de un conjunto de dominó arbitrario, decida si el conjunto es o no solucionable.

En otras palabras, el problema del dominó pregunta si existe un procedimiento efectivo que resuelva correctamente el problema para todos los conjuntos de dominó dados.

En 1966, Berger resolvió el problema del dominó en sentido negativo. Demostró que no puede existir ningún algoritmo para el problema, mostrando cómo traducir cualquier máquina de Turing en un conjunto de teselas de Wang que teselan el plano si y sólo si la máquina de Turing no se detiene. La indecidibilidad del problema de la detención (el problema de comprobar si una máquina de Turing se detiene finalmente) implica entonces la indecidibilidad del problema de teselas de Wang. [4]

Conjuntos de fichas aperiódicos

Azulejos Wang hechos monocromáticos al reemplazar los bordes de cada cuadrante con una forma correspondiente a su color: este conjunto es isomorfo al conjunto mínimo de Jeandel y Rao anterior.

La combinación del resultado de indecidibilidad de Berger con la observación de Wang muestra que debe existir un conjunto finito de mosaicos de Wang que forman mosaicos en el plano, pero solo de forma aperiódica . Esto es similar a un mosaico de Penrose , o la disposición de los átomos en un cuasicristal . Aunque el conjunto original de Berger contenía 20.426 mosaicos, conjeturó que conjuntos más pequeños funcionarían, incluidos subconjuntos de su conjunto, y en su tesis doctoral inédita, redujo el número de mosaicos a 104. En años posteriores, se encontraron conjuntos cada vez más pequeños. [5] [6] [7] [8] Por ejemplo, Karel Culik II publicó un conjunto de 13 mosaicos aperiódicos en 1996. [6]

El conjunto más pequeño de mosaicos aperiódicos fue descubierto por Emmanuel Jeandel y Michael Rao en 2015, con 11 mosaicos y 4 colores. Utilizaron una búsqueda exhaustiva en computadora para demostrar que 10 mosaicos o 3 colores son insuficientes para forzar la aperiodicidad. [8] Este conjunto, que se muestra arriba en la imagen del título, se puede examinar más de cerca en el archivo: Wang 11 tiles.svg .

Generalizaciones

Los mosaicos de Wang se pueden generalizar de varias maneras, todas las cuales también son indecidibles en el sentido anterior. Por ejemplo, los cubos de Wang son cubos de igual tamaño con caras coloreadas, y los colores de los lados se pueden combinar en cualquier teselación poligonal . Culik y Kari han demostrado conjuntos aperiódicos de cubos de Wang. [9] Winfree et al. han demostrado la viabilidad de crear "mosaicos" moleculares hechos de ADN (ácido desoxirribonucleico) que pueden actuar como mosaicos de Wang. [10] Mittal et al. han demostrado que estos mosaicos también pueden estar compuestos de ácido nucleico peptídico (PNA), un imitador artificial estable del ADN. [11]

Aplicaciones

Los mosaicos Wang se han utilizado para la síntesis procedimental de texturas , campos de altura y otros conjuntos de datos bidimensionales grandes y no repetitivos; un pequeño conjunto de mosaicos fuente precalculados o hechos a mano se puede ensamblar de manera muy económica sin repeticiones y periodicidad demasiado obvias. En este caso, los mosaicos aperiódicos tradicionales mostrarían su estructura muy regular; los conjuntos mucho menos restringidos que garantizan al menos dos opciones de mosaico para dos colores laterales dados son comunes porque la capacidad de mosaico se asegura fácilmente y cada mosaico se puede seleccionar de manera pseudoaleatoria. [12] [13] [14] [15] [16]

Las fichas de Wang también se han utilizado en pruebas de decidibilidad de la teoría de autómatas celulares . [17]

En la cultura popular

El cuento " Las alfombras de Wang ", posteriormente ampliado a la novela Diáspora , de Greg Egan , postula un universo, completo con organismos residentes y seres inteligentes, encarnados como mosaicos de Wang implementados por patrones de moléculas complejas. [18]

Véase también

Referencias

  1. ^ Wang, Hao (1961), "Demostración de teoremas mediante reconocimiento de patrones—II", Bell System Technical Journal , 40 (1): 1–41, doi :10.1002/j.1538-7305.1961.tb03975.xWang propone sus fichas y conjetura que no existen conjuntos aperiódicos.
  2. ^ Wang, Hao (noviembre de 1965), "Juegos, lógica y computadoras", Scientific American , 213 (5): 98–106, doi :10.1038/scientificamerican1165-98Presenta el problema del dominó para una audiencia popular.
  3. ^ Renz, Peter (1981), "Demostración matemática: qué es y qué debería ser", The Two-Year College Mathematics Journal , 12 (2): 83–103, doi :10.2307/3027370, JSTOR  3027370.
  4. ^ abc Berger, Robert (1966), "La indecidibilidad del problema del dominó", Memorias de la Sociedad Matemática Americana , 66 : 72, MR  0216954Berger acuña el término "baldosas Wang" y demuestra el primer conjunto aperiódico de ellas.
  5. ^ Robinson, Raphael M. (1971), "Indecidibilidad y no periodicidad para teselación del plano", Inventiones Mathematicae , 12 (3): 177–209, Bibcode :1971InMat..12..177R, doi :10.1007/bf01418780, MR  0297572, S2CID  14259496.
  6. ^ ab Culik, Karel II (1996), "Un conjunto aperiódico de 13 fichas de Wang", Discrete Mathematics , 160 (1–3): 245–251, doi : 10.1016/S0012-365X(96)00118-5 , MR  1417576(Se mostró un conjunto aperiódico de 13 fichas con 5 colores).
  7. ^ Kari, Jarkko (1996), "Un pequeño conjunto aperiódico de teselas Wang", Discrete Mathematics , 160 (1–3): 259–264, doi : 10.1016/0012-365X(95)00120-L , MR  1417578.
  8. ^ de Jeandel, Emmanuel; Rao, Michaël (2021), "Un conjunto aperiódico de 11 mosaicos de Wang", Advances in Combinatorics : 1:1–1:37, arXiv : 1506.06492 , doi :10.19086/aic.18614, MR  4210631, S2CID  13261182. (Mostró un conjunto aperiódico de 11 fichas con 4 colores y demostró que menos fichas o menos colores no pueden ser aperiódicos).
  9. ^ Culik, Karel II; Kari, Jarkko (1995), "Un conjunto aperiódico de cubos de Wang", Journal of Universal Computer Science , 1 (10): 675–686, doi :10.1007/978-3-642-80350-5_57, MR  1392428.
  10. ^ Winfree, E.; Liu, F.; Wenzler, LA; Seeman, NC (1998), "Diseño y autoensamblaje de cristales de ADN bidimensionales", Nature , 394 (6693): 539–544, Bibcode :1998Natur.394..539W, doi :10.1038/28998, PMID  9707114, S2CID  4385579.
  11. ^ Lukeman, P.; Seeman, N.; Mittal, A. (2002), "Nanosistemas híbridos de PNA/ADN", 1.ª Conferencia internacional sobre mecánica molecular/a nanoescala (N-M2-I), Outrigger Wailea Resort, Maui, Hawái.
  12. ^ Stam, Jos (1997), Mapeo de texturas aperiódico (PDF)Introduce la idea de utilizar mosaicos Wang para la variación de textura, con un sistema de sustitución determinista.
  13. ^ Neyret, Fabrice; Cani, Marie-Paule (1999), "Pattern-Based Texturing Revisited", Actas de la 26.ª Conferencia anual sobre gráficos por ordenador y técnicas interactivas - SIGGRAPH '99 (PDF) , Los Ángeles, Estados Unidos: ACM, págs. 235-242, doi : 10.1145/311535.311561, ISBN 0-201-48560-5, Número de identificación del sujeto  11247905Introduce el mosaico estocástico.
  14. ^ Cohen, Michael F. ; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), "Mosaicos Wang para la generación de imágenes y texturas", ACM SIGGRAPH 2003 Papers on - SIGGRAPH '03 (PDF) , Nueva York, NY, EE. UU.: ACM, págs. 287–294, doi :10.1145/1201775.882265, ISBN 1-58113-709-5, S2CID  207162102, archivado desde el original (PDF) el 18 de marzo de 2006.
  15. ^ Wei, Li-Yi (2004), "Mapeo de texturas basado en mosaicos en hardware gráfico", Actas de la Conferencia ACM SIGGRAPH/EUROGRAPHICS sobre hardware gráfico (HWWS '04), Nueva York, NY, EE. UU.: ACM, págs. 55–63, doi :10.1145/1058129.1058138, ISBN 3-905673-15-0, Número de identificación del sujeto  53224612Aplica Wang Tiles para texturizado en tiempo real en una GPU.
  16. ^ . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006), "Mosaicos Wang recursivos para ruido azul en tiempo real", ACM SIGGRAPH 2006 Papers on - SIGGRAPH '06, Nueva York, NY, EE. UU.: ACM, págs. 509–518, doi :10.1145/1179352.1141916, ISBN 1-59593-364-6, Número de identificación del sujeto  11007853. Muestra aplicaciones avanzadas.
  17. ^ Kari, Jarkko (1990), "La reversibilidad de los autómatas celulares 2D es indecidible", Autómatas celulares: teoría y experimentación (Los Alamos, NM, 1989) , Physica D: Nonlinear Phenomena , vol. 45, págs. 379–385, Bibcode :1990PhyD...45..379K, doi :10.1016/0167-2789(90)90195-U, MR  1094882.
  18. ^ Burnham, Karen (2014), Greg Egan, Maestros modernos de la ciencia ficción, University of Illinois Press, págs. 72-73, ISBN 978-0-252-09629-7.

Lectura adicional

Enlaces externos