En informática , una máquina de Turing universal ( UTM ) es una máquina de Turing capaz de calcular cualquier secuencia computable, [1] como lo describe Alan Turing en su artículo seminal "Sobre números computables, con una aplicación al problema de Entscheidung ". El sentido común podría decir que una máquina universal es imposible, pero Turing demuestra que es posible. [a] Sugirió que podemos comparar a un hombre en el proceso de calcular un número real con una máquina que solo es capaz de un número finito de condiciones ; que se llamarán " m -configuraciones". [2] Luego describió el funcionamiento de dicha máquina, como se describe a continuación, y argumentó:
Sostengo que estas operaciones incluyen todas aquellas que se utilizan en el cálculo de un número. [3]
Alan Turing introdujo la idea de una máquina de este tipo en 1936-1937.
Davis presenta un argumento convincente de que la concepción de Turing de lo que ahora se conoce como "la computadora de programa almacenado", de colocar la "tabla de acciones" (las instrucciones para la máquina) en la misma "memoria" que 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 teclean en un teclado... están trabajando en una encarnación de una máquina de Turing", y que "John von Neumann [se basó] en el trabajo de Alan Turing". [4]
Davis sostiene que la máquina de computación automática (ACE) de Turing "anticipó" las nociones de microprogramación ( microcódigo ) y procesadores RISC . [5] Knuth cita el trabajo de Turing en la máquina ACE como el diseño de "hardware para facilitar el enlace de subrutinas"; [6] Davis también hace referencia a este trabajo como el uso de una "pila" de hardware por parte de Turing. [7]
Mientras que la máquina de Turing estaba fomentando la construcción de computadoras , la UTM estaba fomentando el desarrollo de las ciencias de la computación incipientes . Un ensamblador temprano, si no el primero, fue propuesto "por un joven programador brillante" para el EDVAC. [8] El "primer programa serio de von Neumann... [fue] simplemente ordenar datos de manera eficiente". [9] Knuth observa que el retorno de subrutina incrustado en el programa mismo en lugar de en registros especiales es atribuible a von Neumann y Goldstine. [b] Knuth además afirma que
Se puede decir que la primera rutina interpretativa fue la "Máquina Universal de Turing"... Las rutinas interpretativas en el sentido convencional fueron mencionadas por John Mauchly en sus conferencias en la Escuela Moore en 1946..... Turing también participó en este desarrollo; los sistemas interpretativos para la computadora Pilot ACE fueron escritos bajo su dirección. [10]
Davis menciona brevemente los sistemas operativos y compiladores como resultados de la noción de programa como datos. [11]
Con esta codificación de las tablas de acciones como cadenas, se hace posible, en principio, que las máquinas de Turing respondan a 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 particular, o en todas las entradas, conocido como el problema de la detención , se demostró que era, 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 recursivamente enumerable . Según la tesis de Church-Turing , los problemas que puede resolver una máquina de Turing universal son exactamente aquellos problemas que puede resolver un algoritmo o un método de cálculo eficaz , para cualquier definición razonable de esos términos. Por estas razones, una máquina de Turing universal sirve como un estándar con el que 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 puede utilizarse para calcular cualquier otra función computable. El teorema de la máquina de Turing universal demuestra la existencia de dicha función.
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 puede codificarse 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 puede codificarse 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 estados se pueden deducir de la tabla de la función de transición. Los estados y símbolos distinguidos se pueden identificar por su posición, por ejemplo, los dos primeros estados pueden ser por convención los estados de inicio y fin. En consecuencia, cada máquina de Turing se puede codificar como una cadena sobre el alfabeto {0, 1}. Además, convenimos que cada codificación inválida se asigna a una máquina de Turing trivial que se detiene inmediatamente, y que cada máquina de Turing puede tener un número infinito de codificaciones rellenando la codificación con un número arbitrario de (por ejemplo) 1 al final, al igual que funcionan los comentarios 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 FC Hennie y RE Stearns demostraron que dada una máquina de Turing M α que se detiene en la entrada x dentro de N pasos, entonces existe una máquina de Turing universal de múltiples cintas que se detiene en las entradas α , x (dadas en diferentes cintas) en CN log N , donde C es una constante específica de la máquina que no depende de la longitud de la entrada x , pero sí depende del tamaño del alfabeto de M , la cantidad de cintas y la cantidad de estados. Efectivamente, se trata de una simulación, que utiliza la notación Big O de Donald Knuth . [12] El resultado correspondiente para la complejidad espacial en lugar de la complejidad temporal es que podemos simular de una manera que utiliza como máximo celdas CN en cualquier etapa del cálculo, una simulación. [13]
Cuando Alan Turing ideó la idea de una máquina universal, tenía en mente el modelo computacional más simple y lo suficientemente potente como para calcular todas las funciones posibles. Claude Shannon fue el primero en plantear explícitamente 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 utilizaran 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 solo estado.
Marvin Minsky descubrió una máquina de Turing universal de 7 estados y 4 símbolos en 1962 usando sistemas de 2 etiquetas . Desde entonces, Yurii Rogozhin y otros han descubierto otras pequeñas máquinas de Turing universales extendiendo este enfoque de simulación de sistemas de etiquetas. Si denotamos por ( m , n ) la clase de UTM con m estados y n símbolos, se han encontrado las siguientes tuplas: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) y (2, 18). [14] [15] [16] La máquina (4, 6) de Rogozhin usa solo 22 instrucciones, y no se conoce ninguna UTM estándar de menor complejidad descriptiva.
Sin embargo, la generalización del modelo estándar de máquina de Turing admite UTM aún más pequeñas. Una de esas generalizaciones es permitir una palabra repetida infinitamente en uno o ambos lados de la entrada de la máquina de Turing, extendiendo así la definición de universalidad y conocida como universalidad "semidébil" o "débil", respectivamente. Se han dado 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). [17] La prueba de universalidad para la máquina de Turing de 2 estados y 3 símbolos de Wolfram extiende aún más la noción de universalidad débil al permitir ciertas configuraciones iniciales no periódicas. Otras variantes del modelo estándar de máquina de Turing que producen UTM pequeñas incluyen máquinas con múltiples cintas o cintas de múltiples dimensiones y máquinas acopladas con un autómata finito .
Si se permiten múltiples cabezas en una máquina de Turing, entonces no se requieren estados internos; ya que los "estados" se pueden 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 cabezas está situada sobre el triple (2,2A,0). Las reglas luego convierten cualquier triple en otro triple y mueven las 3 cabezas hacia la izquierda o la derecha. Por ejemplo, las reglas podrían convertir (2,2A,0) en (2,1,0) y mover la cabeza hacia la izquierda. Por lo tanto, en este ejemplo, la máquina actúa como una máquina de Turing de 3 colores con estados internos A y B (representados por ninguna letra). El caso de una máquina de Turing de 2 cabezas es muy similar. Por lo tanto, una máquina de Turing de 2 cabezas puede ser universal con 6 colores. No se sabe cuál es el número mínimo de colores necesarios para una máquina de Turing de múltiples cabezas o si es posible una máquina de Turing universal de dos colores con múltiples cabezas. Esto también significa que las reglas de reescritura son Turing completas, ya que las reglas triples son equivalentes a las reglas de reescritura. Si ampliamos la cinta a dos dimensiones con una cabeza que toma una muestra de una letra y sus ocho vecinas, solo se necesitan dos colores, ya que, por ejemplo, un color se puede codificar en un patrón triple vertical como 110.
Además, si la distancia entre los dos cabezales es variable (la cinta tiene "holgura" entre los cabezales), entonces puede simular cualquier sistema de etiquetas Post , algunos de los cuales son universales. [18]
Para aquellos que quieran emprender el desafío de diseñar un UTM exactamente como lo especificó Turing, consulten el artículo de Davies en Copeland (2004). Davies corrige los errores del original y muestra cómo luciría una simulación de muestra. Ejecutó con éxito una simulación (algo simplificada).
El siguiente ejemplo está tomado de Turing (1937). Para obtener más información sobre este ejemplo, consulte Ejemplos de máquinas de Turing .
Turing utilizó siete símbolos {A, C, D, R, L, N, ; } para codificar cada 5-tupla; como se describe en el artículo Máquina de Turing , sus 5-tuplas son solo de tipos N1, N2 y N3. El número de cada " m- configuración" (instrucción, estado) se representa con "D" seguido de una cadena unaria de A, p. ej. "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" permanecen como están.
Después de codificar, cada tupla de 5 se "ensambla" en una cadena en el orden que 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 se separa por ";", es decir:
Este código lo colocó en casillas alternadas (las "casillas F"), dejando vacías las "casillas E" (las que se pueden borrar). El ensamblaje final del código en la cinta para la máquina U consiste en colocar dos símbolos especiales ("e") uno después del otro, luego el código separado en casillas alternadas y, por último, el símbolo de dos puntos " :: " (los espacios en blanco se muestran aquí con "." para mayor claridad):
La tabla de acciones de la máquina U (tabla de transición de estados) es responsable de decodificar los símbolos. La tabla de acciones de Turing lleva un registro de su ubicación con los marcadores "u", "v", "x", "y", "z" colocándolos en "cuadrados E" 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 DAA de "configuración m" actual. La tabla de acciones de la máquina U moverá estos símbolos de un lado a otro (borrándolos y colocándolos en diferentes ubicaciones) a medida que avanza el cálculo:
La tabla de acciones de Turing para su máquina U es muy compleja.
Roger Penrose ofrece ejemplos de formas de codificar instrucciones para la máquina universal utilizando únicamente símbolos binarios {0, 1} o {espacio en blanco, marca |}. Penrose va más allá y escribe todo el código de su máquina U. Afirma que realmente es un código de máquina U, un número enorme que abarca casi dos páginas completas de 1 y 0. [19]
Asperti y Ricciotti describieron un UTM multicinta definido mediante la composición de máquinas elementales con una semántica muy simple, en lugar de proporcionar explícitamente su tabla de acciones completa. Este enfoque era lo suficientemente modular como para permitirles demostrar formalmente la corrección de la máquina en el asistente de pruebas Matita . [20]
sección 1.4, "Máquinas como cuerdas y la máquina universal de Turing" y 1.7, "Demostración del teorema 1.9"
