Las fichas 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 . Se modelan visualmente usando mosaicos cuadrados con colores en cada lado. Se define un conjunto de dichos mosaicos (por ejemplo, como en la ilustración), luego se aplican copias de estos mosaicos entre sí con la condición de hacer coincidir los colores de los lados, pero sin rotación o reflejo simétrico de los mosaicos.
La pregunta principal sobre el conjunto de fichas de Van es si pueden enlosar un plano o no, es decir, si un plano se puede rellenar de esta manera. La siguiente pregunta es si se puede llenar en un patrón periódico.
En 1961, Wang conjeturó que si un número finito de mosaicos Wang puede enlosar un plano, entonces existe un mosaico periódico , es decir, un mosaico que es invariante bajo la traducción de vectores en una red bidimensional como papel tapiz. También señaló que esta conjetura implica la existencia de un algoritmo que determina si un conjunto finito dado de mosaicos Wang puede enlosar un plano [1] [2] . La idea de limitar la conexión de fichas adyacentes se originó en el juego de dominó , por lo que las fichas de Wang también se conocen como dominó de Wang [3] , y el problema algorítmico de determinar si las fichas pueden enlosar un plano se conoce como el problema del dominó [ 4] .
Según el estudiante de Van, Robert Berger [4] ,
El problema del dominó se ocupa de la clase de todos los conjuntos de dominó. La tarea es determinar para cada juego de fichas de dominó si es posible o no un mosaico. Decimos que el Problema del Dominó es decidible o indecidible , dependiendo de si existe o no un algoritmo que, dado un conjunto de un conjunto arbitrario de fichas de dominó, determine si el problema de mosaico para este conjunto es decidible o no.
En otras palabras, el problema del dominó pregunta si existe un método eficiente que resuelva correctamente el problema para conjuntos de dominó dados.
En 1966, Berger resolvió el problema del dominó al refutar la conjetura de Wang. Demostró que no podía haber ningún algoritmo al mostrar cómo transformar cualquier máquina de Turing en un conjunto de mosaicos de Wang para que los mosaicos cubrieran el plano si y solo si la máquina de Turing no se detuviera. De la imposibilidad de resolver el problema de la detención (el problema de verificar si la máquina de Turing finalmente se detiene), se sigue la imposibilidad de resolver el problema de mosaico de Wang [4] [4] .
La combinación del resultado de Berger con la observación de Wang muestra que debe haber un conjunto finito de mosaicos de Wang que cubren el plano, pero solo de forma no periódica . Esta propiedad la posee el mosaico de Penrose y la disposición de los átomos en un cuasicristal . Aunque el conjunto original de Berger contenía 20.426 mosaicos, sugirió que también podrían existir conjuntos más pequeños, incluidos subconjuntos de su conjunto original, y en su tesis inédita redujo el número de mosaicos a 104. Más tarde se encontraron conjuntos incluso más pequeños [5] [6] [ 7] . Por ejemplo, el conjunto de 11 mosaicos y 4 colores anterior es un conjunto no periódico, y fue descubierto por Emmanuel Jandel y Michael Rao en 2015 mediante una búsqueda exhaustiva para demostrar que 10 mosaicos o 3 colores no son suficientes para ser aperiódico [8] .
Las fichas de Wang se pueden generalizar de varias maneras, y todas ellas también son indecidibles en el sentido anterior. Por ejemplo, los cubos Wang son cubos del mismo tamaño con caras coloreadas que deben coincidir en color al crear mosaicos poliédricos ( panales ) . Kulik y Kari mostraron conjuntos no periódicos de cubos de Wang [9] . Winfrey y otros han mostrado la posibilidad de crear "tejas" moleculares basadas en ADN (ácido desoxirribonucleico) que pueden actuar como las tejas de Wang [10] . Mittal y otros han demostrado que los ácidos peptidonucleicos (PNA), semejanzas estables de ADN artificial, se pueden componer con estos mosaicos [11] .
Los mosaicos Wang se han convertido recientemente en un medio popular para crear texturas algorítmicas , campos de elevación y otros grandes conjuntos de datos 2D que no se repiten. Se puede ensamblar una pequeña cantidad de mosaicos precalculados o hechos a mano de manera rápida y económica sin repeticiones o periodicidades obvias. En este caso, las teselaciones ordinarias no periódicas mostrarían su estructura. Los conjuntos mucho menos restrictivos que brindan al menos dos opciones para dos colores laterales cualesquiera son más aceptables porque el mosaico se logra fácilmente y cada mosaico se puede elegir de forma pseudoaleatoria [12] [13] [14] [15] . Los mosaicos de Wang también se utilizan para comprobar la decidibilidad de la teoría de los autómatas celulares [16] .
El cuento de Greg Egan " Van's Carpet ", más tarde expandido a la novela "Diaspora" , habla de un universo lleno de organismos y seres pensantes en forma de mosaicos de Van, formados por patrones de moléculas complejas [17] .
| mosaicos geometricos | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Periódico |
| ||||||||
| aperiódico |
| ||||||||
| Otro |
| ||||||||
| Por configuración de vértice |
| ||||||||