Las fichas de Wang (o dominó 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 mediante azulejos cuadrados con un color en cada lado. Se selecciona un conjunto de dichos mosaicos y las copias de los mosaicos se organizan una al lado de la otra con colores coincidentes, sin rotarlos ni reflejarlos.
La pregunta básica acerca de un conjunto de mosaicos de Wang es si puede formar mosaicos en 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 en un patrón periódico.
En 1961, Wang conjeturó que si un conjunto finito de mosaicos de Wang puede formar mosaicos en el plano, entonces también existe un mosaico periódico , que, matemáticamente, es un mosaico que es invariante bajo traslaciones de vectores en una red bidimensional. Esto se puede comparar con el mosaico periódico de 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 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 Wang también se conocen como dominó Wang. [3] El problema algorítmico de determinar si un conjunto de mosaicos puede formar mosaicos en el plano se conoció como el problema del dominó . [4]
Según el alumno de Wang, Robert Berger , [4]
El problema del dominó trata de la clase de todos los conjuntos de dominó. Consiste en decidir, para cada conjunto de dominó, si tiene solución o no. Decimos que el Problema de 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 solucionable o no.
En otras palabras, el problema del dominó pregunta si existe un procedimiento eficaz que resuelva correctamente el problema para todos los conjuntos de dominó dados.
En 1966, Berger resolvió el problema del dominó de 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 de Wang que recubren el avión 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 finalmente se detiene) implica entonces la indecidibilidad del problema de la teselación de Wang. [4]
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 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 funcionarían conjuntos más pequeños, incluidos subconjuntos de su conjunto, y en su doctorado 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 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 informática exhaustiva 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 .
Las tejas 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 del mismo tamaño con caras coloreadas y los colores de los lados se pueden combinar en cualquier mosaico 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 peptídico nucleico (PNA), un imitador artificial estable del ADN. [11]
Los mosaicos Wang se han utilizado para la síntesis procesal 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 mosaicos aperiódicos tradicionales mostrarían su estructura muy regular; Son comunes los conjuntos mucho menos restringidos que garantizan al menos dos opciones de mosaicos para dos colores de lados dados porque la capacidad de mosaico se garantiza fácilmente y cada mosaico se puede seleccionar de forma pseudoaleatoria. [12] [13] [14] [15] [16]
Los mosaicos de Wang también se han utilizado en pruebas de decidibilidad de la teoría de autómatas celulares . [17]
El cuento " Las alfombras de Wang ", ampliado posteriormente 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]
