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.

Este conjunto de 11 Wang los azulejos enladrillarán el plano pero único aperiodicamente.

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.

Domino Problema
Ejemplo de Wang tessellation con 13 azulejos.

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]

Conjuntos Aperiódicos de azulejos

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.

Generalizaciones

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]

Aplicaciones

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]

Ve también

Referencias
  1. Wang, Hao (1961), «Proving theorems by pattern recognition—II», Bell System Technical Journal 40 (1): 1-41, doi:10.1002/j.1538-7305.1961.tb03975.x.. Wang proposes his tiles, and conjectures that there are no aperiodic sets.
  2. Wang, Hao (November 1965), «Games, logic and computers», Scientific American: 98-106.. Presents the domino problem for a popular audience.
  3. Renz, Peter (1981), «Mathematical proof: What it is and what it ought to be», The Two-Year College Mathematics Journal 12 (2): 83-103, doi:10.2307/3027370..
  4. Berger, Robert (1966), «The undecidability of the domino problem», Memoirs of the American Mathematical Society 66: 72.. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.
  5. Robinson, Raphael M. (1971), «Undecidability and nonperiodicity for tilings of the plane», Inventiones Mathematicae 12: 177-209, Bibcode:1971InMat..12..177R, doi:10.1007/bf01418780..
  6. Culik, Karel, II (1996), «An aperiodic set of 13 Wang tiles», Discrete Mathematics 160 (1-3): 245-251, doi:10.1016/S0012-365X(96)00118-5.. (Showed an aperiodic set of 13 tiles with 5 colors).
  7. Kari, Jarkko (1996), «A small aperiodic set of Wang tiles», Discrete Mathematics 160 (1-3): 259-264, doi:10.1016/0012-365X(95)00120-L..
  8. Jeandel, Emmanuel; Rao, Michael (2015), «An aperiodic set of 11 Wang tiles», CoRR, Bibcode:2015arXiv150606492J.. (Showed an aperiodic set of 11 tiles with 4 colors)}
  9. Culik, Karel, II; Kari, Jarkko (1995), «An aperiodic set of Wang cubes», Journal of Universal Computer Science 1 (10): 675-686, doi:10.1007/978-3-642-80350-5_57..
  10. Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C. (1998), «Design and self-assembly of two-dimensional DNA crystals», Nature 394: 539-544, Bibcode:1998Natur.394..539W, PMID 9707114, doi:10.1038/28998..
  11. Lukeman, P.; Seeman, N.; Mittal, A. (2002), «Hybrid PNA/DNA nanosystems», 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii..
  12. Stam, Jos (1997), Aperiodic Texture Mapping.. Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
  13. Neyret, Fabrice; Cani, Marie-Paule (1999), «Pattern-Based Texturing Revisited», ACM SIGGRAPH 1999, Los Angeles, United States: ACM, pp. 235--242, doi:10.1145/311535.311561.. Introduces stochastic tiling.
  14. Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), «Wang tiles for image and texture generation», ACM SIGGRAPH 2003, New York, NY, USA: ACM, pp. 287-294, ISBN 1-58113-709-5, doi:10.1145/1201775.882265, archivado desde el original el 18 de marzo de 2006..
  15. Wei, Li-Yi (2004), «Tile-based texture mapping on graphics hardware», Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM, pp. 55-63, ISBN 3-905673-15-0, doi:10.1145/1058129.1058138.. Applies Wang Tiles for real-time texturing on a GPU.
  16. . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006), «Recursive Wang tiles for real-time blue noise», ACM SIGGRAPH 2006, New York, NY, USA: ACM, pp. 509-518, ISBN 1-59593-364-6, doi:10.1145/1179352.1141916.. Shows advanced applications.
  17. Kari, Jarkko (1990), «Reversibility of 2D cellular automata is undecidable», Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena 45 (1-3), pp. 379-385, Bibcode:1990PhyD...45..379K, doi:10.1016/0167-2789(90)90195-U..
  18. Burnham, Karen (2014), Greg Egan, Modern Masters of Science Fiction, University of Illinois Press, pp. 72-73, ISBN 9780252096297..
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.