Las fichas de Wang (o dominós 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 . Están modelados visualmente por mosaicos cuadrados con un color en cada lado. Se selecciona un conjunto de tales mosaicos, y las copias de los mosaicos se organizan una al lado de la otra con colores coincidentes, sin rotarlas ni reflejarlas.
La pregunta básica sobre un conjunto de mosaicos de Wang es si puede enlosar el plano o no, es decir, si un plano infinito completo se puede llenar de esta manera. La siguiente pregunta es si esto se puede hacer en un patrón periódico.
Problema de dominó
En 1961, Wang conjeturó que si un conjunto finito de mosaicos de Wang puede enlosar el plano, entonces existe también un mosaico periódico , es decir, un mosaico que es invariante bajo traslaciones por vectores en una celosía bidimensional, como un patrón de papel tapiz. También observó que esta conjetura implicaría la existencia de un algoritmo para decidir si un conjunto finito dado de mosaicos de Wang puede enlosar 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 mosaicos puede enlosar el plano se conoció como el problema del dominó . [4]
Según el alumno de Wang, Robert Berger , [4]
El problema del dominó se ocupa de la clase de todos los juegos de dominó. Consiste en decidir, para cada juego 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, decidirá si el conjunto es o no solucionable.
En otras palabras, el problema del dominó se pregunta si existe un procedimiento eficaz que resuelva correctamente el problema para todos los juegos de dominó dados.
En 1966, Berger resolvió el problema del dominó en forma negativa. Demostró que no puede existir ningún algoritmo para el problema, mostrando cómo traducir cualquier máquina de Turing en un conjunto de mosaicos Wang que mosaicos el plano si y solo si la máquina de Turing no se detiene. La indecidibilidad del problema de la detención (el problema de probar si una máquina de Turing finalmente se detiene) implica entonces la indecidibilidad del problema de los mosaicos de Wang. [4]
Conjuntos de azulejos aperiódicos
La combinación del resultado de indecidibilidad de Berger con la observación de Wang muestra que debe existir un conjunto finito de baldosas de Wang que recubren 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 los conjuntos más pequeños funcionarían, incluidos subconjuntos de su conjunto, y en su Ph.D. inédito. tesis, 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 fichas aperiódicas en 1996. [6]
El conjunto más pequeño de azulejos aperiódicos fue descubierto por Emmanuel Jeandel y Michael Rao en 2015, con 11 azulejos y 4 colores. Utilizaron una búsqueda exhaustiva por 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 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 Wang son cubos de igual tamaño con caras coloreadas y los colores laterales se pueden combinar en cualquier teselado poligonal . Culik y Kari han demostrado conjuntos aperiódicos de cubos Wang. [9] Winfree y col. han demostrado la viabilidad de crear "mosaicos" moleculares hechos de ADN (ácido desoxirribonucleico) que pueden actuar como mosaicos de Wang. [10] Mittal y col. 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 convertido recientemente en una herramienta popular 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 demasiado obvias y sin periodicidad. En este caso, los revestimientos 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 pseudoaleatoriamente. [12] [13] [14] [15] [16]
Los mosaicos de Wang también se han utilizado en pruebas de decidibilidad de la teoría de los autómatas celulares . [17]
En la cultura popular
El cuento Wang's Carpets , ampliado más tarde a la novela Diaspora , 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]
Ver también
- Rompecabezas de combinación de bordes
- Rompecabezas de la eternidad II
- Percy Alexander MacMahon
Referencias
- ^ 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.x. Wang propone sus mosaicos y conjetura que no hay conjuntos aperiódicos.
- ^ Wang, Hao (noviembre de 1965), "Juegos, lógica y computadoras", Scientific American , 213 (5): 98–106, doi : 10.1038 / scientificamerican1165-98. Presenta el problema del dominó para una audiencia popular.
- ^ Renz, Peter (1981), "Prueba 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.
- ^ a b c Berger, Robert (1966), "La indecidibilidad del problema del dominó", Memorias de la American Mathematical Society , 66 : 72, MR 0216954. Berger acuña el término "baldosas de Wang" y muestra el primer conjunto aperiódico de ellas.
- ^ Robinson, Raphael M. (1971), "Indecidibilidad y no periodicidad para teselaciones del plano", Inventiones Mathematicae , 12 (3): 177-209, Bibcode : 1971InMat..12..177R , doi : 10.1007 / bf01418780 , MR 0297572.
- ^ a b Culik, Karel, II (1996), "An aperiodic set of 13 Wang tiles", Discrete Mathematics , 160 (1-3): 245-251, doi : 10.1016 / S0012-365X (96) 00118-5 , MR 1417576. (Mostró un conjunto aperiódico de 13 azulejos con 5 colores).
- ^ Kari, Jarkko (1996), "A small aperiodic set of Wang tiles", Discrete Mathematics , 160 (1-3): 259-264, doi : 10.1016 / 0012-365X (95) 00120-L , MR 1417578.
- ^ a b Jeandel, Emmanuel; Rao, Michael (2021), "An aperiodic set of 11 Wang tiles", CoRR , arXiv : 1506.06492 , Bibcode : 2015arXiv150606492J , doi : 10.19086 / aic.18614. (Mostró un conjunto aperiódico de 11 fichas con 4 colores)}
- ^ 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.
- ^ 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.
- ^ Lukeman, P .; Seeman, N .; Mittal, A. (2002), "Nanosistemas híbridos de PNA / ADN", Primera Conferencia Internacional sobre Mecánica Nanoescala / Molecular (N-M2-I), Outrigger Wailea Resort, Maui, Hawái.
- ^ Stam, Jos (1997), Mapeo de texturas aperiódico (PDF). Introduce la idea de usar baldosas Wang para la variación de textura, con un sistema de sustitución determinista.
- ^ Neyret, Fabrice; Cani, Marie-Paule (1999), "Pattern-Based Texturing Revisited", Actas de la 26ª conferencia anual sobre gráficos por computadora y técnicas interactivas - SIGGRAPH '99 (PDF) , Los Ángeles, Estados Unidos: ACM, págs. 235–242 , doi : 10.1145 / 311535.311561 , ISBN 0201485605. Introduce el mosaico estocástico.
- ^ Cohen, Michael F .; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), "Wang tiles for image and texture generation", 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, archivado desde el original (PDF) el 2006-03-18.
- ^ Wei, Li-Yi (2004), "Mapeo de texturas basado en mosaicos en hardware de gráficos", Actas de la Conferencia ACM SIGGRAPH / EUROGRAPHICS sobre hardware de gráficos (HWWS '04) , Nueva York, NY, EE. UU.: ACM, págs. 55– 63, doi : 10.1145 / 1058129.1058138 , ISBN 3-905673-15-0. Aplica Wang Tiles para texturizado en tiempo real en una GPU.
- ^ . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006), "Recursive Wang tiles for real-time blue noise", 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. Muestra aplicaciones avanzadas.
- ^ Kari, Jarkko (1990), "La reversibilidad de los autómatas celulares 2D es indecidible", Autómatas celulares: teoría y experimento (Los Alamos, NM, 1989) , Physica D: Nonlinear Phenomena , 45 , pp. 379-385, Bibcode : 1990PhyD. ..45..379K , doi : 10.1016 / 0167-2789 (90) 90195-U , MR 1094882.
- ^ Burnham, Karen (2014), Greg Egan , Maestría moderna en ciencia ficción, University of Illinois Press, págs. 72–73, ISBN 9780252096297.
Otras lecturas
- Grünbaum, Branko ; Shephard, GC (1987), Tilings and Patterns , Nueva York: WH Freeman, ISBN 0-7167-1193-1.
enlaces externos
- Página de Steven Dutch que incluye muchas imágenes de teselaciones aperiódicas.
- Demostración animada de un método ingenuo de ordenamiento en teselas de Wang : requiere Javascript y HTML5