Azulejos Wang

Azulejos Wang (o Dominó Wang), primero propuestos por el matemático, lógico, y filósofo Hao Wang en 1961, es una clase de sistemas formales. Son modelados visualmente por azulejos cuadrados con un color en cada lado. Un conjunto de tales azulejos está seleccionado, y las copias de los azulejos son puesto lado a lado con colores iguales, sin rotarlos ni reflejándolos.

La cuestión básica sobre un conjunto de Wang los azulejos es si puede enladrillar el plano o no, por ejemplo, si un plano infinito entero puede ser llenado de este modo. La siguiente pregunta es si esto puede ser hecho en un patrón periódico.

En 1961, Wang conjeturó que si un conjunto finito de Azulejos Wang pueden enladrillar un plano, entonces allí existe también un enladrillamiento periódico, por ejemplo, un enladrillando que es invariante bajo traducciones por vectores en un 2-enrejado dimensional, como un wallpaper patrón. También observe que esta conjetura implicaría la existencia de un algoritmo para decidir si un conjunto finito dado de Wang los azulejos pueden enladrillar el avión.^[1]​^[2]​ La idea de limitarse a emparejar azulejos adyacentes para emparejar así todos ocurre en el juego de dominoes, así los azulejos Wang son también sabidos como Wang dominoes.^[3]​ El problema algorítmico de determinar si un conjunto de azulejo puede enladrillar el plano devino sabido como el problema del dominó.^[4]​

Según el estudiante de Wang, Robert Berger,^[4]​

El Problema del Dominó trata la clase de todos los conjuntos de dominó. Consiste en decidir, para cada conjunto de dominó, si o no es resoluble. Decimos que el Problema del dominó es decible o indecible según si allí existe o no existe un algoritmo qué, dado las especificaciones de un arbitrarios domino conjunto, decidirá si o no el conjunto es resoluble.

En otras palabras, el domino el problema pregunta si hay un procedimiento eficaz que correctamente resuelve el problema para todo dado domino conjuntos.

En 1966, Berger solucionó el domino problema en el negativo. Pruebe que ningún algoritmo para el problema puede existir, por mostrar cómo para traducir cualquier Turing máquina a un conjunto de Wang azulejos que azulejos el avión si y sólo si el Turing máquina no para. El undecidability del problema de la parada (el problema de probar si un Turing máquina finalmente para) entonces implica el undecidability de Wang está enladrillando problema.^[4]​

Combinando Berger undecidability resultado con Wang la observación muestra que allí tiene que existir un conjunto finito de Wang azulejos que azulejos el avión, pero único aperiodically. Esto es similar a un Penrose que enladrilla, o el arreglo de átomos en un quasicrystal. A pesar de que Berger el conjunto original contuvo 20,426 azulejos, él conjectured que los conjuntos más pequeños trabajarían, incluyendo subconjuntos de su conjunto, y en su inédito Ph.D. Tesis, reduzca el número de azulejos a 104. En años más tardíos, cada vez más los conjuntos más pequeños estuvieron encontrados.^[5]​^[6]​^[7]​^[8]​ Por ejemplo, un conjunto de 13 aperiodic los azulejos estuvo publicado por Karel Culik II en 1996.

El conjunto más pequeño de aperiodic los azulejos estuvo descubierto por Emmanuel Jeandel y Michael Rao en 2015, con 11 azulejos y 4 colores. Utilizaron una búsqueda de ordenador exhaustiva para probar que 10 azulejos o 3 colores son insuficientes de forzar aperiodicity.^[8]​ Este conjunto, mostrado encima en la imagen de título, puede ser examinado más estrechamente en Archivo:Wang 11 azulejos.svg.

Wang Los azulejos pueden ser generalizados en varias maneras, todo de los cuales son también indecidibles en el encima sentido. Por ejemplo, Wang los cubos son iguales-sized cubos con colored caras y colores de lado pueden ser emparejados en cualquier polygonal tessellation. Culik Y Kari ha demostrado aperiodic conjuntos de Wang cubos.^[9]​ Winfree Et al. Ha demostrado la viabilidad de crear los azulejos "moleculares" hicieron de ADN (deoxyribonucleic ácido) que puede actuar tan Wang azulejos.^[10]​ Mittal Et al. Ha mostrado que estos azulejos también pueden ser compuestos de ácido nucleico de péptido (PNA), un estable artificial mimic de ADN.^[11]​

Wang Azulejos haber recientemente devenir una herramienta popular para síntesis procesal de texturas, heightfields, y otro grandes y nonrepeating bidimensional conjuntos de dato; un conjunto pequeño de precomputed o mano-azulejos de fuente hecha pueden ser reunidos muy baratamente sin repeticiones demasiado obvias y sin periodicidad. En este caso, tradicional aperiodic tilings mostraría su estructura muy regular; mucho menos conjuntos cohibidos que garantía al menos dos elecciones de azulejo para cualquier dos lado dado los colores son comunes porque tileability es fácilmente asegurado y cada azulejo puede ser seleccionado pseudorandomly.^[12]​^[13]​^[14]​^[15]​^[16]​

Wang Los azulejos también han sido utilizados en celulares automata teoría decidability pruebas.^[17]​

El cuento Wang Alfombras, más tarde expandidos a la Diáspora novel, por Greg Egan, postulados un universo, completo con organismos residentes y seres inteligentes, encarnados como Wang los azulejos implementaron por patrones de moléculas complejas.^[18]​

• Percy Alexander MacMahon