Wang tile

format_list_bulleted Contenido keyboard_arrow_down
ImprimirCitar
Este conjunto de 11 baldosas Wang tejará el avión pero sólo aperiodicamente.
Las

fichas Wang (o dominós 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 dichos mosaicos y se colocan copias de los mosaicos una al lado de la otra con colores coincidentes, sin girarlos o reflejarlos.

La pregunta básica sobre un conjunto de mosaicos Wang es si puede colocar mosaicos en 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ó

Ejemplo de tessellation Wang con 13 fichas.

En 1961, Wang conjeturó que si un conjunto finito de mosaicos de Wang puede enlosar el plano, también existe un mosaico periódico, que, matemáticamente, es un mosaico que es invariante bajo traslaciones por vectores en una red bidimensional. Esto se puede comparar con el mosaico periódico en un patrón de papel tapiz, donde el patrón general es una repetición de un 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. 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. El problema algorítmico de determinar si un conjunto de teselas puede teselar el plano se conoció como el problema del dominó.

Según el alumno de Wang, Robert Berger,

El problema Domino se ocupa de la clase de todos los juegos de dominó. Consiste en decidir, para cada conjunto domino, ya sea o no es solvable. Decimos que el problema Domino es decidable o indecidable de acuerdo a si existe o no existe un algoritmo que, dadas las especificaciones de un conjunto de dominó arbitrario, decidirá si el conjunto es o no solvable.

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

En 1966, Berger resolvió negativamente el problema del dominó. Demostró que no puede existir ningún algoritmo para el problema, al mostrar cómo traducir cualquier máquina de Turing en un conjunto de mosaicos de Wang que recubren 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 eventualmente se detiene) implica entonces la indecidibilidad del problema de mosaico de Wang.

Conjuntos aperiódicos de fichas

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

Combinar el resultado de indecidibilidad de Berger con la observación de Wang muestra que debe existir un conjunto finito de mosaicos de Wang que enlosan el plano, pero solo aperiódicamente. 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. tesis, redujo el número de fichas a 104. En años posteriores, se encontraron conjuntos cada vez más pequeños. Por ejemplo, Karel Culik II publicó un conjunto de 13 fichas aperiódicas en 1996.

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. Este conjunto, que se muestra arriba en la imagen del título, se puede examinar más de cerca en File:Wang 11 tiles.svg.

Generalizaciones

Las fichas 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 laterales se pueden combinar en cualquier mosaico poligonal. Culik y Kari han demostrado conjuntos aperiódicos de cubos de Wang. Winfree et al. han demostrado la viabilidad de crear "tejas" moleculares; hecho de ADN (ácido desoxirribonucleico) que puede actuar como mosaicos de Wang. 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.

Aplicaciones

Los mosaicos de Wang se han utilizado para la síntesis de procedimientos 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, las teselaciones aperiódicas 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 forma pseudoaleatoria.

Los mosaicos de Wang también se han utilizado en las pruebas de decidibilidad de la teoría de los autómatas celulares.

En la cultura popular

La historia corta Wang's Carpets, luego ampliada a la novela Diaspora, de Greg Egan, postula un universo completo con organismos residentes y seres inteligentes, encarnados como mosaicos Wang implementados por patrones de moléculas complejas.

Contenido relacionado

Numerales mayas

Función cúbica

En matemáticas, a función cúbica es una función de la forma f()x)=ax3+bx2+cx+d,{displaystyle f(x)=ax^{3}+bx^{2}+cx+d,} es decir, una función polinomio...

Factorización de curva elíptica de Lenstra

La factorización de curva elíptica de Lenstra o el método de factorización de curva elíptica es un tiempo de ejecución subexponencial rápido, algoritmo...
Más resultados...
Tamaño del texto:
undoredo
format_boldformat_italicformat_underlinedstrikethrough_ssuperscriptsubscriptlink
save