Máquina universal de Turing

En informática, una máquina de Turing universal (UTM) es una máquina de Turing que puede simular una máquina de Turing arbitraria con una entrada arbitraria. La máquina universal esencialmente logra esto leyendo tanto la descripción de la máquina a simular como la entrada a esa máquina desde su propia cinta. Alan Turing introdujo la idea de tal máquina en 1936-1937. Se considera que este principio es el origen de la idea de una computadora con programa almacenado utilizada por John von Neumann en 1946 para el "Instrumento de computación electrónica" que ahora lleva el nombre de von Neumann: la arquitectura de von Neumann.

En términos de complejidad computacional, una máquina de Turing universal de múltiples cintas solo necesita ser más lenta por un factor logarítmico en comparación con las máquinas que simula.

Introducción

Cada máquina de Turing calcula una determinada función computable parcial fija a partir de las cadenas de entrada sobre su alfabeto. En ese sentido se comporta como una computadora con un programa fijo. Sin embargo, podemos codificar la tabla de acciones de cualquier máquina de Turing en una cadena. Por tanto, podemos construir una máquina de Turing que espera en su cinta una cadena que describa una tabla de acciones seguida de una cadena que describa la cinta de entrada, y calcula la cinta que habría calculado la máquina de Turing codificada. Turing describió tal construcción con completo detalle en su artículo de 1936:

"Es posible inventar una sola máquina que se puede utilizar para calcular cualquier secuencia computable. Si esta máquina U se suministra con una cinta en el principio de la cual se escribe la S.D ["descripcion estándar" de una tabla de acción] de alguna máquina de computación M, entonces U computará la misma secuencia M."

Computadora con programa almacenado

Davis presenta un argumento persuasivo de que la concepción de Turing de lo que ahora se conoce como 'la computadora de programa almacenado', de colocar la 'mesa de acción', las instrucciones para la máquina, en la misma "memoria" como los datos de entrada, influyó fuertemente en la concepción de John von Neumann de la primera computadora estadounidense de símbolos discretos (en oposición a la analógica): la EDVAC. Davis cita a la revista Time en este sentido, que "todos los que tocan un teclado... están trabajando en una encarnación de una máquina de Turing", y que "John von Neumann [construido] sobre el trabajo de Alan Turing" (Davis 2000:193 citando la revista Time del 29 de marzo de 1999).

Davis argumenta que la computadora del motor de computación automática (ACE) de Turing "anticipó" las nociones de microprogramación (microcódigo) y procesadores RISC (Davis 2000:188). Knuth cita el trabajo de Turing en la computadora ACE como el diseño de "hardware para facilitar el enlace de subrutinas" (Knuth 1973:225); Davis también hace referencia a este trabajo como el uso de Turing de una 'pila' de hardware. (Davis 2000:237 nota al pie 18).

Así como la Máquina de Turing fomentaba la construcción de computadoras, la UTM fomentaba el desarrollo de las incipientes ciencias de la computación. Un ensamblador temprano, si no el primero, fue propuesto "por un joven programador destacado" para el EDVAC (Davis 2000:192). El "primer programa serio... [fue] simplemente ordenar datos de manera eficiente" (Davis 2000: 184). Knuth observa que el retorno de la subrutina incrustado en el propio programa en lugar de en registros especiales es atribuible a von Neumann y Goldstine. Knuth además afirma que

La primera rutina interpretativa puede decirse que es la "Máquina de Turing Universal"... Las rutinas interpretativas en el sentido convencional fueron mencionadas por John Mauchly en sus conferencias en la Escuela Moore en 1946... Turing participó también en este desarrollo; los sistemas de interpretación para el ordenador Pilot ACE fueron escritos bajo su dirección.

—Knuth 1973:226

Davis menciona brevemente los sistemas operativos y los compiladores como resultados de la noción de programa como datos (Davis 2000:185).

Algunos, sin embargo, podrían plantear problemas con esta evaluación. En ese momento (mediados de la década de 1940 a mediados de la década de 1950), un grupo relativamente pequeño de investigadores estaba íntimamente involucrado con la arquitectura de las nuevas "computadoras digitales". Hao Wang (1954), un joven investigador en ese momento, hizo la siguiente observación:

La teoría de Turing de las funciones computables antedated pero no ha influido mucho en la extensa construcción de computadoras digitales. Estos dos aspectos de la teoría y la práctica se han desarrollado casi totalmente independientemente unos de otros. La razón principal es sin duda que los lógicos están interesados en preguntas radicalmente diferentes de aquellas con las que los matemáticos aplicados e ingenieros eléctricos están principalmente preocupados. No puede, sin embargo, no golpear uno como bastante extraño que a menudo los mismos conceptos se expresan por términos muy diferentes en los dos desarrollos.

—Wang 1954, 1957:63

Wang esperaba que su artículo "conectara los dos enfoques". De hecho, Minsky confirma esto: 'que la primera formulación de la teoría de la máquina de Turing en modelos similares a los de una computadora aparece en Wang (1957)' (Minsky 1967:200). Minsky continúa demostrando la equivalencia de Turing de una máquina contadora.

Con respecto a la reducción de las computadoras a simples modelos equivalentes de Turing (y viceversa), la designación de Wang por parte de Minsky como quien hizo "la primera formulación" está abierto a debate. Si bien tanto el artículo de Minsky de 1961 como el artículo de Wang de 1957 son citados por Shepherdson y Sturgis (1963), también citan y resumen con cierto detalle el trabajo de los matemáticos europeos Kaphenst (1959), Ershov (1959) y Peter (1958). Los nombres de los matemáticos Hermes (1954, 1955, 1961) y Kaphenst (1959) aparecen en las bibliografías tanto de Sheperdson-Sturgis (1963) como de Elgot-Robinson (1961). Otros dos nombres de importancia son los investigadores canadienses Melzak (1961) y Lambek (1961). Para obtener más información, consulte los equivalentes de la máquina de Turing; Las referencias se pueden encontrar en la máquina de registro.

Teoría matemática

Con esta codificación de tablas de acción como cadenas, en principio, las máquinas de Turing pueden responder preguntas sobre el comportamiento de otras máquinas de Turing. Sin embargo, la mayoría de estas preguntas son indecidibles, lo que significa que la función en cuestión no se puede calcular mecánicamente. Por ejemplo, el problema de determinar si una máquina de Turing arbitraria se detendrá en una entrada en particular, o en todas las entradas, conocido como el problema de la detención, demostró ser, en general, indecidible en el artículo original de Turing. El teorema de Rice muestra que cualquier pregunta no trivial sobre la salida de una máquina de Turing es indecidible.

Una máquina de Turing universal puede calcular cualquier función recursiva, decidir cualquier lenguaje recursivo y aceptar cualquier lenguaje enumerable recursivamente. De acuerdo con la tesis de Church-Turing, los problemas que puede resolver una máquina universal de Turing son exactamente aquellos problemas que puede resolver un algoritmo o un método efectivo de cálculo, para cualquier definición razonable de esos términos. Por estas razones, una máquina de Turing universal sirve como estándar contra el cual comparar sistemas computacionales, y un sistema que puede simular una máquina de Turing universal se llama Turing completo.

Una versión abstracta de la máquina de Turing universal es la función universal, una función computable que se puede utilizar para calcular cualquier otra función computable. El teorema UTM prueba la existencia de tal función.

Eficiencia

Sin pérdida de generalidad, se puede suponer que la entrada de la máquina de Turing está en el alfabeto {0, 1}; cualquier otro alfabeto finito se puede codificar sobre {0, 1}. El comportamiento de una máquina de Turing M está determinado por su función de transición. Esta función también se puede codificar fácilmente como una cadena sobre el alfabeto {0, 1}. El tamaño del alfabeto de M, el número de cintas que tiene y el tamaño del espacio de estado se pueden deducir de la tabla de funciones de transición. Los estados y símbolos distinguidos se pueden identificar por su posición, p. los dos primeros estados pueden ser, por convención, los estados de inicio y finalización. En consecuencia, cada máquina de Turing se puede codificar como una cadena sobre el alfabeto {0, 1}. Además, convenimos en que cada codificación no válida se asigna a una máquina de Turing trivial que se detiene de inmediato, y que cada máquina de Turing puede tener una cantidad infinita de codificaciones rellenando la codificación con un número arbitrario de (digamos) 1's al final, al igual que los comentarios funcionan en un lenguaje de programación. No debería sorprender que podamos lograr esta codificación dada la existencia de un número de Gödel y la equivalencia computacional entre las máquinas de Turing y las funciones μ-recursivas. De manera similar, nuestra construcción asocia a cada cadena binaria α, una máquina de Turing M_α.

Partiendo de la codificación anterior, en 1966 F. C. Hennie y R. E. Stearns mostraron que dada una máquina de Turing M_α que se detiene en la entrada x dentro N pasos, entonces existe una máquina de Turing universal de múltiples cintas que se detiene en las entradas α, x (se entrega en diferentes cintas) en CN log N, donde C es una constante de máquina específica que no depende de la longitud de la entrada x, pero depende de M 's tamaño del alfabeto, número de cintas y número de estados. Efectivamente esto es un ${displaystyle {mathcal}left(Nlog {N}right)}$ simulación, usando la notación Big O de Donald Knuth. El resultado correspondiente para la complejidad del espacio en lugar de la complejidad del tiempo es que podemos simular de una manera que utiliza a la mayoría CN células en cualquier etapa del cálculo, una ${displaystyle {Mathcal}(N)}$ simulación.

Máquinas más pequeñas

Cuando a Alan Turing se le ocurrió la idea de una máquina universal, tenía en mente el modelo informático más simple lo suficientemente potente como para calcular todas las funciones posibles que se pueden calcular. Claude Shannon planteó explícitamente por primera vez la cuestión de encontrar la máquina de Turing universal más pequeña posible en 1956. Demostró que dos símbolos eran suficientes siempre que se usaran suficientes estados (o viceversa), y que siempre era posible intercambiar estados por símbolos. También demostró que no podía existir una máquina de Turing universal de un estado.

Marvin Minsky descubrió una máquina de Turing universal de 7 estados y 4 símbolos en 1962 utilizando sistemas de 2 etiquetas. Desde entonces, Yurii Rogozhin y otros han encontrado otras pequeñas máquinas de Turing universales al extender este enfoque de simulación del sistema de etiquetas. Si denotamos por (m, n) la clase de UTMs con estados m y símbolos n las siguientes tuplas se han encontrado: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) y (2, 18). La máquina de Rogozhin (4, 6) usa solo 22 instrucciones y no se conoce ningún UTM estándar de menor complejidad descriptiva.

Sin embargo, la generalización del modelo de máquina de Turing estándar admite UTM aún más pequeños. Una de esas generalizaciones es permitir una palabra infinitamente repetida en uno o ambos lados de la entrada de la máquina de Turing, extendiendo así la definición de universalidad y conocida como "semi-débil" o "débil" universalidad, respectivamente. Se han proporcionado pequeñas máquinas de Turing débilmente universales que simulan el autómata celular de la Regla 110 para los pares de estado-símbolo (6, 2), (3, 3) y (2, 4). La prueba de universalidad para la máquina de Turing de 2 estados y 3 símbolos de Wolfram amplía aún más la noción de universalidad débil al permitir ciertas configuraciones iniciales no periódicas. Otras variantes del modelo de máquina de Turing estándar que producen UTM pequeños incluyen máquinas con múltiples cintas o cintas de múltiples dimensiones y máquinas acopladas con un autómata finito.

Máquinas sin estados internos

Si se permiten varios cabezales en una máquina de Turing, no se requieren estados internos; como "estados" se puede codificar en la cinta. Por ejemplo, considere una cinta con 6 colores: 0, 1, 2, 0A, 1A, 2A. Considere una cinta como 0,0,1,2,2A,0,2,1 donde una máquina de Turing de 3 cabezales está situada sobre el triple (2,2A,0). Luego, las reglas convierten cualquier triple en otro triple y mueven las 3 caras hacia la izquierda o hacia la derecha. Por ejemplo, las reglas pueden convertir (2,2A,0) en (2,1,0) y mover la cabeza hacia la izquierda. Así, en este ejemplo, la máquina actúa como una máquina de Turing de 3 colores con estados internos A y B (representados sin letra). El caso de una máquina de Turing de 2 cabezas es muy similar. Así, una máquina de Turing de 2 cabezas puede ser universal con 6 colores. No se sabe cuál es el menor número de colores necesarios para una máquina de Turing de cabezales múltiples o si es posible una máquina de Turing universal de 2 colores con cabezales múltiples. También significa que las reglas de reescritura son Turing completas ya que las reglas triples son equivalentes a las reglas de reescritura. Al extender la cinta a dos dimensiones con una cabeza que muestra una letra y sus 8 vecinos, solo se necesitan 2 colores, ya que, por ejemplo, un color se puede codificar en un patrón triple vertical como 110.

Ejemplo de codificación de máquina universal

Para aquellos que aceptarían el desafío de diseñar un UTM exactamente como lo especificó Turing, vean el artículo de Davies en Copeland (2004:103ff). Davies corrige los errores en el original y muestra cómo se vería una ejecución de muestra. Afirma haber ejecutado con éxito una simulación (algo simplificada).

El siguiente ejemplo está tomado de Turing (1936). Para obtener más información sobre este ejemplo, consulte Ejemplos de máquinas de Turing.

Turing usó siete símbolos { A, C, D, R, L, N,; } para codificar cada tupla de 5; como se describe en el artículo Máquina de Turing, sus 5 tuplas son solo de tipo N1, N2 y N3. El número de cada "m‑configuration" (instrucción, estado) está representado por "D" seguido de una cadena unaria de A's, p. "q3" = DAAA. De manera similar, codifica los símbolos en blanco como "D", el símbolo "0" como "DC", el símbolo "1" como DCC, etc. Los símbolos "R", "L" y "N" permanecer como está.

Después de codificar, cada tupla de 5 se "ensambla" en una cadena en orden como se muestra en la siguiente tabla:

Finalmente, los códigos para las cuatro tuplas de 5 se unen en un código que comienza con ";" y separados por ";" es decir.:

Este código lo colocó en cuadrados alternos: los "F-squares" – dejando los "E-cuadrados" (aquellos sujetos a borrado) vacíos. El ensamblaje final del código en la cinta para la máquina U consiste en colocar dos símbolos especiales ("e") uno tras otro, luego el código separado en cuadrados alternos y, por último, los dos puntos dobles. símbolo "::" (los espacios en blanco se muestran aquí con "." para mayor claridad):

La tabla de acción (tabla de transición de estado) de U-machine es responsable de decodificar los símbolos. La tabla de acción de Turing realiza un seguimiento de su lugar con los marcadores "u", "v", "x", "y", "z" colocándolos en "E-squares" a la derecha del "símbolo marcado" – por ejemplo, para marcar la instrucción actual z se coloca a la derecha de ";" x mantiene el lugar con respecto a la actual "m‑configuration" DAA. La tabla de acción de U-machine desplazará estos símbolos (borrándolos y colocándolos en diferentes ubicaciones) a medida que avanza el cálculo:

La mesa de acción de Turing para su máquina U es muy complicada.

Otros comentaristas (sobre todo Penrose 1989) proporcionan ejemplos de formas de codificar instrucciones para la máquina Universal. Al igual que Penrose, la mayoría de los comentaristas usan solo símbolos binarios, es decir, solo símbolos {0, 1} o {en blanco, marca | }. Penrose va más allá y escribe todo su código U-máquina (Penrose 1989: 71-73). Afirma que realmente es un código U-máquina, un número enorme que abarca casi 2 páginas completas de 1's y 0's. Para los lectores interesados en codificaciones más simples para la máquina Post-Turing, la discusión de Davis en Steen (Steen 1980: 251ff) puede ser útil.

Asperti y Ricciotti describieron un UTM de múltiples cintas definido por la composición de máquinas elementales con una semántica muy simple, en lugar de proporcionar explícitamente su tabla de acción completa. Este enfoque fue lo suficientemente modular como para permitirles probar formalmente la corrección de la máquina en el asistente de pruebas de Matita.

Programación de máquinas de Turing

Varios lenguajes de alto nivel están diseñados para ser compilados en una máquina de Turing. Los ejemplos incluyen Laconic y Turing Machine Descriptor.