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 fundamental "Sobre números computables, con una aplicación al Entscheidungsproblem ". 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 sólo es capaz de cumplir un número finito de condiciones ; que se llamará " m -configuraciones". [2] Luego describió el funcionamiento de dicha máquina, como se describe a continuación, y argumentó:
Mi opinión es que estas operaciones incluyen todas aquellas que se utilizan en el cálculo de un número. [3]
Alan Turing presentó la idea de una máquina de este tipo en 1936-1937.
Davis presenta un argumento persuasivo de que la concepción de Turing de lo que ahora se conoce como "la computadora con 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 John La concepción de von Neumann de la primera computadora estadounidense de símbolo discreto (a diferencia de la analógica): la EDVAC . Davis cita a la revista Time en este sentido, que "todo aquel que toca un teclado... está trabajando en una encarnación de una máquina de Turing", y que "John von Neumann [construyó] sobre el trabajo de Alan Turing". [4]
Davis argumenta que la computadora Automatic Computing Engine (ACE) de Turing "anticipó" las nociones de microprogramación ( microcódigo ) y procesadores RISC . [5] Knuth cita el trabajo de Turing en la computadora ACE como diseño de "hardware para facilitar el enlace de subrutinas"; [6] Davis también hace referencia a este trabajo como el uso que hace Turing de una "pila" de hardware. [7]
Mientras la máquina de Turing fomentaba la construcción de ordenadores , la UTM fomentaba el desarrollo de las incipientes ciencias informáticas . Un ensamblador temprano, si no el primero, fue propuesto "por un joven programador destacado" 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 integrado en el programa mismo en lugar de en registros especiales es atribuible a von Neumann y Goldstine. [b] Knuth afirma además que
Se puede decir que la primera rutina interpretativa fue la "Máquina Universal de Turing"... John Mauchly mencionó las rutinas interpretativas en el sentido convencional 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 los compiladores como resultados de la noción de programa como datos. [11]
Con esta codificación de tablas de acciones como cadenas, es posible, en principio, que las máquinas de Turing respondan preguntas sobre el comportamiento de otras máquinas de Turing. Sin embargo, la mayoría de estas cuestiones son indecidibles , lo que significa que la función en cuestión no se puede calcular mecánicamente. Por ejemplo, en el artículo original de Turing se demostró que el problema de determinar si una máquina arbitraria de Turing se detendrá en una entrada particular o en todas las entradas, conocido como problema de detención , es, en general, indecidible. El teorema de Rice muestra que cualquier cuestión no trivial sobre la producción 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 pueden resolverse mediante 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 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 universal de Turing es la función universal , una función computable que puede usarse para calcular cualquier otra función computable. El teorema UTM demuestra la existencia de tal 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 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 estados se pueden deducir de la tabla de funciones de transición. Los estados y símbolos distinguidos pueden identificarse 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 en que cada codificación no válida se asigne 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 (digamos) unos al final, al igual que los comentarios. trabajar 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 α .
A partir 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 cintas múltiples que se detiene en las entradas α , x (dada 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í del tamaño del alfabeto de M , el número de cintas y el número de estados. Efectivamente, se trata de una simulación que utiliza la notación O grande 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 utilice como máximo células CN en cualquier etapa del cálculo, una simulación. [13]
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 utilizaran suficientes estados (o viceversa), y que siempre era posible intercambiar estados por símbolos. También demostró que no podía existir ninguna 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 utilizando sistemas de 2 etiquetas . Desde entonces, Yurii Rogozhin y otros han encontrado otras pequeñas máquinas universales de Turing ampliando 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 de Rogozhin (4, 6) utiliza sólo 22 instrucciones y no se conoce ningún UTM estándar de menor complejidad descriptiva.
Sin embargo, generalizar el modelo estándar de máquina de Turing admite UTM aún más pequeños. Una de esas generalizaciones es permitir una palabra repetida infinitamente en uno o ambos lados de la entrada de la máquina de Turing, ampliando así la definición de universalidad y conocida como universalidad "semidébil" o "débil", 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 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 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 estándar de máquina de Turing 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 .
Si se permiten varias cabezas en una máquina de Turing, entonces no se requieren estados internos; como "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). Luego, las reglas convierten cualquier triple en otro triple y mueven las 3 cabezas hacia la izquierda o hacia la derecha. Por ejemplo, las reglas podrían 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 (no representados por ninguna letra). El caso de una máquina de Turing de dos cabezas es muy similar. Así, una máquina de Turing de dos 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 múltiples cabezales o si es posible una máquina de Turing universal de 2 colores con múltiples cabezales. También significa que las reglas de reescritura son completas de Turing, ya que las reglas triples son equivalentes a reglas de reescritura. Extendiendo la cinta a dos dimensiones con una cabeza que toma una muestra de una letra y sus 8 vecinas, solo se necesitan 2 colores, como 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 aceptarían el desafío de diseñar un UTM exactamente como lo especificó Turing, consulte el artículo de Davies en Copeland (2004). Davies corrige los errores del original y muestra cómo sería una ejecució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 tuplas; Como se describe en el artículo Máquina de Turing , sus 5 tuplas son solo de los tipos N1, N2 y N3. El número de cada " m -configuración" (instrucción, estado) está representado por "D" seguido de una cadena unaria de A, por ejemplo, "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 es.
Después de codificar, cada 5 tuplas se "ensambla" en una cadena en el orden que se muestra en la siguiente tabla:
Finalmente, los códigos de las cuatro 5 tuplas se unen en un código que comienza con ";" y separados por ";" es decir:
Este código lo colocó en cuadrados alternativos, los "cuadrados F", dejando los "cuadrados E" (aquellos sujetos a borrado) vacíos. El montaje 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 el símbolo de dos puntos " :: " (Aquí se muestran espacios en blanco con "." para mayor claridad):
La tabla de acciones de la máquina U (tabla de transición de estado) es responsable de decodificar los símbolos. La tabla de acciones de Turing realiza un seguimiento de su lugar 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 al DAA actual de "configuración m". La tabla de acciones de la máquina U trasladará 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.
Roger Penrose proporciona ejemplos de formas de codificar instrucciones para la máquina Universal utilizando sólo 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 unos y ceros. [19]
Asperti y Ricciotti describieron un UTM multicinta definido componiendo máquinas elementales con una semántica muy simple, en lugar de dar explícitamente su tabla de acciones completa. Este enfoque fue lo suficientemente modular como para permitirles demostrar formalmente la corrección de la máquina en el asistente de prueba Matita . [20]
sección 1.4, "Máquinas como cuerdas y la máquina de Turing universal" y 1.7, "Demostración del teorema 1.9"
