Azulejo Wang

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

La pregunta fundamental sobre un conjunto de teselas de Wang es si puede recubrir el plano o no, es decir, si se puede llenar un plano infinito completo de esta manera. La siguiente pregunta es si esto se puede hacer siguiendo un patrón periódico.

En 1961, Wang conjeturó que si un conjunto finito de teselas de Wang puede cubrir el plano, entonces también existe un teselado periódico , que, matemáticamente, es un teselado invariante bajo traslaciones por vectores en una red bidimensional. Esto puede compararse 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 teselas de Wang puede cubrir el plano. ^{[ 1 ] [ 2 ]} La idea de restringir que las teselas adyacentes coincidan entre sí aparece en el juego de dominó , por lo que las teselas de Wang también se conocen como dominós de Wang. ^{[ 3 ]} El problema algorítmico de determinar si un conjunto de teselas puede cubrir el plano se conoció como el problema del dominó . ^{[ 4 ]}

Según el alumno de Wang, Robert Berger , ^{[ 4 ]}

El problema del dominó trata sobre la clase de todos los conjuntos de dominós. Consiste en decidir, para cada conjunto de dominós, si es resoluble o no. 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ós arbitrario, decida si dicho conjunto es resoluble o no.

En otras palabras, el problema del dominó plantea la cuestión de si existe un procedimiento eficaz que resuelva correctamente el problema para todos los conjuntos de fichas 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 a un conjunto de teselas de Wang que recubren el plano si y solo si la máquina de Turing no se detiene. La indecidibilidad del problema de la parada (el problema de comprobar si una máquina de Turing se detiene finalmente) implica entonces la indecidibilidad del problema del recubrimiento 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 teselas de Wang que recubren el plano, pero solo de forma aperiódica . Esto es similar a un recubrimiento de Penrose o a la disposición de átomos en un cuasicristal . Aunque el conjunto original de Berger contenía 20.426 teselas, conjeturó que conjuntos más pequeños funcionarían, incluyendo subconjuntos de su conjunto, y en su tesis doctoral inédita, redujo el número de teselas a 104. En años posteriores, se encontraron conjuntos aún más pequeños. ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ]} Por ejemplo, Karel Culik II publicó un conjunto de 13 teselas aperiódicas en 1996. ^{[ 6 ]}

El conjunto más pequeño de teselas aperiódicas fue descubierto por Emmanuel Jeandel y Michael Rao en 2015, con 11 teselas y 4 colores. Utilizaron una búsqueda computacional exhaustiva para demostrar que 10 teselas o 3 colores son insuficientes para forzar la aperiodicidad. ^{[ 8 ]}

Las teselas de Wang pueden generalizarse de diversas maneras, todas ellas 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 pueden coincidir 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 "teselas" moleculares hechas de ADN (ácido desoxirribonucleico) que pueden actuar como teselas de Wang. ^{[ 10 ]} Mittal et al. han demostrado que estas teselas también pueden estar compuestas de ácido nucleico peptídico (PNA), un imitador artificial estable del ADN. ^{[ 11 ]}

Los mosaicos de 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 forma muy económica sin repeticiones ni periodicidad demasiado evidentes. En este caso, los teselados aperiódicos tradicionales mostrarían su estructura muy regular; son comunes los conjuntos mucho menos restringidos que garantizan al menos dos opciones de mosaico para cualquier par de colores de lado dados, porque la capacidad de teselado se asegura fácilmente y cada mosaico se puede seleccionar de forma pseudoaleatoria. ^{[ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ]}

Las teselas 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 ", posteriormente ampliado a la novela Diáspora , de Greg Egan , postula un universo, con organismos residentes y seres inteligentes, encarnados como teselas de Wang implementadas mediante patrones de moléculas complejas. ^{[ 18 ]}

• Rompecabezas de emparejamiento de bordes

• Grünbaum, Branko ; Shephard, GC (1987), Tilings and Patterns , Nueva York: WH Freeman, ISBN 0-7167-1193-1.

• La página de Steven Dutch incluye muchas imágenes de teselaciones aperiódicas.
• Demostración animada de un método de teselado de Wang sencillo : requiere Javascript y HTML5.