Las fichas de Wang (dominó) fueron inventadas por Hao Wang en 1961 por problemas matemáticos, pero fueron ampliamente utilizadas en juegos para crear gráficos de fichas. Gracias a ellos, los resultados no parecen repetitivos, tanto en texturas 2D como en modelos 3D con mosaico.
Parece que los mosaicos de Van también son capaces de ejecutar máquinas de Turing y, por lo tanto, son completos de Turing, lo que significa que pueden ejecutar cualquier programa.
Esta es una declaración increíble e incomprensible, por lo que en esta publicación exploraré un poco este tema.
Brevemente sobre Van Tiles
Las fichas Van son fichas rectangulares en las que cada una de las caras solo puede corresponder a otras caras específicas, pero para cualquier cara en particular hay varias fichas posibles que pueden corresponder a esa cara. Al hacer coincidir caras, quiero decir que se conectan sin problemas sin crear artefactos visuales o signos de una costura entre las baldosas.
Esta propiedad es útil para gráficos, ya que le permite crear gráficos de mosaico sin interrupciones, pero la configuración de la ubicación de los mosaicos puede ser completamente aleatoria, siempre que todas las caras sean compatibles entre sí. El resultado son gráficos en mosaico, que no son como los que se repiten, porque los patrones visuales se vuelven mucho menos perceptibles que los gráficos en mosaico tradicionales.
Puede encontrar ejemplos gráficos, información más detallada y enlaces a Shadertoy aquí:
Wang Tiling .
Aquí hay un ejemplo que creé. Mis gráficos son "programadores de arte", pero espero que la idea sea clara. El dibujo se compone de 16 fichas, y para cada cara hay dos tipos diferentes de caras.
Brevemente sobre las máquinas de Turing
Las máquinas de Turing fueron inventadas en 1936 por Alan Turing como una computadora generalizada, para lo cual se demostró que puede ejecutar cualquier algoritmo.
La máquina Turing se compone de varios componentes principales: cintas de memoria, cabezales de lectura / escritura y máquinas de estado.
La cinta de memoria tiene una longitud infinita, es decir, tiene una capacidad de almacenamiento infinita, y al principio se inicializa solo con ceros.
El cabezal de lectura / escritura comienza desde una cierta posición de la cinta y puede leer / escribir valores, y también moverse hacia la izquierda y hacia la derecha a lo largo de la cinta.
La máquina de estado controla el cabezal de lectura / escritura.
La máquina de estado sabe en qué estado se encuentra y tiene reglas sobre qué hacer en cada estado cuando lee un valor de la cinta.
Por ejemplo, en el estado A, si se lee 0 de la cinta, entonces la regla puede ser escribir 1 en la posición actual de la cinta, mover el cabezal de lectura / escritura a la derecha o ir al estado B. El estado B puede tener una lógica completamente diferente y puede realizar la transición volver al estado A, o permanecer en el estado B, o pasar a un estado completamente diferente.
Usando una lógica tan simple de transición entre estados, se puede ejecutar cualquier algoritmo de computadora.
La máquina de Turing también puede tener un "Estado de detención", lo que significa que el programa ha completado la ejecución y la respuesta ha sido calculada.
Buscando algunos programas. Se puede ver fácilmente. que con el tiempo, terminarán o estarán en un bucle infinito y nunca se detendrán. Algunos programas están ubicados entre ellos, son complejos y no es tan fácil determinar si alguna vez se detendrán. Turing demostró que no existe una solución general para determinar si la máquina de Turing se detendrá (es un programa de computadora), y esto se denomina
problema de detención . En general, la única forma de averiguar si un programa se detiene es esperar. Es decir, de hecho, en el caso general, las respuestas a esta pregunta son “sí” o “todavía no”, sin embargo, en el caso de muchos programas específicos, puede ver que después del lanzamiento terminarán con el tiempo.
Wang Tile Calculations
Resulta que los mosaicos de Wang pueden simular una máquina de Turing, es decir, son completos de Turing, lo que significa que pueden ejecutar cualquier algoritmo informático.
Para darnos cuenta de esto, necesitamos una columna de mosaicos Van que indique el estado de la máquina Turing en un punto particular en el tiempo, comenzando en el tiempo 0 en la columna más a la izquierda. Pondremos mosaicos en la columna de la derecha con todas las reglas de las caras, y luego crearemos una columna a la derecha, y así sucesivamente, hasta que el programa termine (o haremos esto para siempre si no termina). Si selecciona el conjunto correcto de mosaicos, entonces verificar el cumplimiento de las reglas de las caras en el proceso de organización de los mosaicos será suficiente para completar la máquina de Turing.
Veamos un ejemplo simple que tiene las siguientes reglas lógicas de máquina de estado:
- Cuando la máquina está en el estado A, en el caso de leer 0, escribimos 1, movemos la cabeza de lectura / escritura hacia abajo y pasamos al estado B.
- Cuando la máquina está en el estado A, en el caso de la lectura 1, el programa se detiene (cambia al estado final).
- Cuando la máquina está en el estado B, en el caso de leer 0, escribimos 1, movemos la cabeza de lectura-escritura hacia arriba y pasamos al estado A.
- Cuando la máquina está en estado B, en el caso de la lectura 1, el programa se detiene (pasa al estado final)
Unidad de cinta
En primer lugar, necesitamos un almacenamiento permanente para la cinta. Para hacer esto, necesitamos los siguientes dos mosaicos:
Para probar su trabajo, podemos preparar un segmento de la cinta con algunos valores (crear una columna de mosaicos Van) y asegurarnos de que los únicos mosaicos Van adecuados ubicados al lado de la columna inicial sean mosaicos que transfieran los valores 0 y 1 hacia adelante en el tiempo sin cambiar ellos.
En el siguiente diagrama, inicializamos la cinta con el valor 0101 en la columna más a la izquierda (tiempo 0). Al tener solo mosaicos con caras compatibles, vemos que los valores en la memoria se almacenan para siempre. ¡Hemos implementado una unidad de memoria!
Comenzaremos a demostrar nuestro ejemplo con la memoria inicializada a 0, y la figura anterior simplemente muestra la persistencia de la memoria.
Máquina de estado del cabezal de lectura-escritura
El cabezal de lectura / escritura de una máquina Turing se presenta como parte de la información de la cara. Por lo tanto, además de la cara que almacena 0 o 1, si el cabezal de lectura / escritura está en él, también almacena el estado de la máquina de estados.
En nuestro ejemplo, se utilizan dos estados (sin incluir el estado final): A y B. Si se lee 1, entonces, en cualquiera de los estados (A o B), el programa finaliza.
Para manejar esto, necesitamos los siguientes mosaicos:
Ahora que tenemos las reglas para la transición al estado final (reglas 2 y 4), necesitamos entender cómo implementar las reglas que controlan el cambio de un estado a otro (reglas 1 y 3).
Mover el cabezal de lectura / escritura
La regla 1 establece que si estamos en el estado A y leemos 0, debemos escribir 1, mover la cabeza de lectura / escritura hacia abajo y pasar al estado B.
Necesitamos este mosaico para leer 0 en el estado A, escribir 1 como salida, y ordenar al mosaico a continuación que entre en el estado B.
El mosaico debajo del actual puede tener un valor de 0 o 1; sin conocer un valor específico, debemos guardarlo, pero aceptar el cabezal de lectura / escritura y estar en estado B. Para esto, necesitamos dos mosaicos: uno para 0 en la cinta en esta posición, el otro para 1 en la cinta.
La regla 3 establece que si estamos en el estado B y leemos 0, debemos escribir 1, mover la cabeza de lectura-escritura hacia arriba y pasar al estado A.
Para hacer esto, necesitamos una construcción similar a la construcción para la regla 1, pero no nos movemos hacia abajo, sino hacia arriba. Las siguientes tres fichas darán el resultado deseado:
Azulejos iniciales de columna
Percibiremos los límites del área de simulación como si tuvieran una cara "x".
Esto significa que para crear la columna inicial (máquina de Turing en el tiempo 0) necesitamos dos mosaicos especiales. Se necesita un mosaico para almacenar el valor 0 en la cinta, que inicializa la cinta, y otro mosaico para almacenar la posición del cabezal de lectura / escritura en el estado A, que es nuestro estado inicial.
Estas dos fichas son:
Conjunto listo de azulejos
Aquí está el conjunto completo de 12 mosaicos que utilizaremos:
Simulación completa
Aquí está el diseño original de nuestra máquina Turing en el momento 0. Tenga en cuenta que este es uno de los posibles estados iniciales, pero este es el estado que hemos elegido. No dejamos la oportunidad de elegir dónde comienza el cabezal de lectura / escritura, y su presencia también. Si seguimos solo las reglas de las caras, entonces podemos obtener 4 o 0 cabezas de lectura-escritura, o cualquier número entre ellas.
A partir de aquí, para crear la segunda columna, comenzamos desde la parte superior y bajamos, eligiendo un mosaico que coincida con las restricciones de la cara que toca. En este primer paso, la cabeza lee 0, escribe 1, se mueve hacia abajo y pasa al estado B.
Aquí está el segundo paso, donde la cabeza lee 0, escribe 1, se mueve hacia arriba y pasa al estado A.
Aquí está el último paso en el que la cabeza lee 1 y entra en el estado final, lo que indica que el programa está completo.
El programa finalizó y nos dio un valor de salida de 0110, o 6. Estos valores de salida no son particularmente significativos, pero otros programas pueden producir resultados significativos. Por ejemplo, podemos obligar a una máquina de Turing a sumar dos números, y la salida será la suma de estos dos números.
Detalle importante
Aquí debemos mencionar un detalle importante que no consideramos anteriormente, y que no se menciona en la mayoría de las explicaciones de las máquinas Turing en las fichas Van.
Al colocar el segundo mosaico para el tiempo 2, la única restricción en las caras es que el mosaico debe tener x en la parte superior y 1 en la izquierda. De hecho, debido a esto, la situación se vuelve ambigua, porque no está claro cuál de los dos mosaicos que se muestran a continuación deben seleccionarse.
Entonces, ¿cómo elegimos el correcto?
La respuesta es que simplemente asumimos y elegimos uno de ellos. Si en este caso se selecciona el mosaico incorrecto, cuando pasemos al siguiente mosaico, buscaremos un mosaico con x en la parte superior y B0 a la izquierda. Tal mosaico no existe, por lo que no podemos colocar el mosaico. Cuando esto sucede, debemos volver al último mosaico y probar una de las otras opciones.
Esto es, desafortunadamente, cuando se simulan máquinas de Turing usando fichas de Wang, hay literalmente un proceso de prueba y error, pero al menos es bastante manejable. Realmente complica un poco los cálculos en el sombreador de píxeles (o en otros dispositivos con alto paralelismo), pero los costos no son mucho mayores.
Conclusión y enlaces
Algunos de los enlaces a continuación tratan sobre los mosaicos Wang y las máquinas de Turing, pero las discusiones no parecen adherirse estrictamente a las máquinas de Turing. Por ejemplo, puede notar que en algunos ejemplos, los datos pueden regresar "en el tiempo": cuando el programa finaliza, la respuesta está en cinta en el momento 0 de la máquina Turing, a pesar de que estos datos no estaban allí en el momento 0. Esto muestra que los mosaicos de Wang pueden hacer los cálculos solos, no solo simulando máquinas de Turing, sino que no sé exactamente cómo se llamará esta técnica.
Además, si está interesado en saber qué es útil en la computación usando los mosaicos Wang, entonces personalmente no podré imaginar casos de su aplicación práctica. Sin embargo, los científicos parecen haber descubierto que el ADN puede actuar de la misma manera que las fichas de Van en el sentido de que las conexiones se hacen solo entre caras compatibles. Gracias a esto, los cálculos basados en el ADN ahora se están investigando en función del proceso de computación utilizando los mosaicos de Wang. ¡Un tema bastante interesante!
Aquí está la implementación del cálculo de números primos usando mosaicos Wang en Shadertoy en el sombreador de píxeles WebGL:
Shadertoy: Wang Tiles: PrimeGeneratorAquí hay algunos videos más geniales sobre los autos de Turing y el problema de detenerse:
Máquinas de Turing explicadas - ComputerphileTuring y el problema de la detención - ComputerphileY aquí hay algunos enlaces más:
Computación con azulejosWikipedia: Van tilesWang Tiles y Máquinas TuringWang Tiles - 1Aquí hay algunos artículos científicos:
Computación con azulejosComputabilidad de las inclinaciones