En ciencias de la computación, una máquina universal de Turing (UTM) es una máquina de Turing que puede simular una máquina de Turing arbitraria en la entrada arbitraria. La máquina universal esencialmente logra esto mediante la lectura de tanto la descripción de la máquina a ser simulada como también la entrada misma de su propia cinta. Alan Turing introdujo esta máquina en 1936-1937. Este modelo es considerado por algunos (por ejemplo, Davis, 2000) el origen del computador de programa almacenado — usado por John von Neumann (1946) para el "instrumento de computación electrónica" que ahora lleva el nombre de von Neumann: la arquitectura de von Neumann. Es también conocida como una máquina de computación universal, máquina universal.
En términos de complejidad computacional, una máquina universal de Turing de múltiple cinta sólo necesita ser más lenta por un factor logarítmico, comparada con las máquinas que simula.
Toda máquina de Turing computa una cierta función parcial computable fija desde las cadenas de entrada sobre su alfabeto. En ese sentido, se comporta como un computador con un programa fijo. Sin embargo, la tabla de acción, de cualquier máquina de Turing, puede ser codificada en una cadena. Así, se puede construir una máquina de Turing que espera en su cinta una cadena describiendo la tabla de acción (de otra máquina de Turing), seguida de una cadena que describe la cinta de entrada (de la otra máquina), y luego computa la cinta que la máquina de Turing codificada habría computado. Turing describió tal construcción en completo detalle en su artículo de 1936:
Davis hace un argumento persuasivo que la concepción de Turing, de lo que ahora es conocido como "el computador de programa almacenado", que coloca la "tabla de acción" - las instrucciones para la máquina — en la misma "memoria" que los datos de entrada, fuertemente influenció la concepción de John von Neumann del primer computador de símbolo discreto, el EDVAC, (en oposición al computador analógico). A este efecto, Davis cita a la revista Time, "todo el mundo que teclea en 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" (Davis 2000:193 citando a la revista Time del 29 de marzo de 1999).
Davis hace un caso indicando que el computador de Turing, el Automatic Computing Engine (ACE), "anticipó" las nociones de microprogramación (microcódigo) y procesadores RISC (Davis 2000:188). Donald Knuth cita el trabajo de Turing en el computador ACE como designando "hardware para facilitar la vinculación a subrutinas"; Davis también hace referencia a este trabajo como el uso por Turing de un hardware de "stack" (Davis 2000:237 Nota 18).
A medida que la máquina de Turing fomentaba la construcción de computadores, la UTM estaba alentando el desarrollo de la incipiente ciencia de la computación. Un temprano, si no el primer, ensamblador fue propuesto "por un joven programador hot-shot" para el EDVAC (Davis 2000:192). El "primer programa serio de von Neumann... [fue] para simplemente ordenar datos eficientemente" (Davis 2000:184). Knuth observa que el retorno de subrutina incrustado en el propio programa en lugar de registros especiales es atribuible a von Neumann y Goldstine. Knuth además afirma que
Davis menciona brevemente a los sistemas operativos y a 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 el momento (desde mediados de 1940 hasta mediados de la década de 1950) un relativamente pequeño grupo de investigadores estaban íntimamente involucrados con la arquitectura de las nuevas "computadoras digitales". Hao Wang (1954), un joven investigador en este entonces, hizo la siguiente observación:
Wang esperaba que su artículo sería "conectar 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 como computadora aparece en Wang (1957)" (Minsky 1967:200). Minsky pasa a demostrar la equivalencia de Turing de una máquina de contador.
Con respecto a la reducción de los computadores a simples modelos Turing equivalentes (y viceversa), es un debate abierto la designación de Minsky de que Wang hizo "la primera formulación". Mientras que tanto el artículo de Minsky de 1961 y el artículo de Wang de 1957 son citados por Shepherdson y Sturgis (1963), también citan y sumarizan con cierto detalle el trabajo de los matemáticos europeos Kaphenst (1959), Ershov (1959), y Péter (1958). Los nombres de matemáticos Hermes (1954, 1955, 1961) y Kaphenst (1959) aparecen en las bibliografías de Sheperdson-Sturgis (1963) y Elgot-Robinson (1961). Otros dos nombres de importancia son los investigadores canadienses Melzak (1961) y Lambek (1961). Para mucho más, vea equivalentes de la máquina de Turing; las referencias pueden ser encontradas en máquina de registro.
Con esta codificación de tablas de acción como cadenas en principio se hace posible para máquinas de Turing 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 puede ser calculada mecánicamente. Por ejemplo, el problema de determinar si una máquina de Turing arbitraria se detendrá en una entrada, o en todas las entradas, conocido como el problema de la parada, en el artículo original de Turing ha demostrado ser, en general, indecidible. El teorema de Rice muestra que cualquier pregunta no trivial sobre la salida de una máquina de Turing es indecidible.
Una máquina universal de Turing puede calcular cualquier función recursiva, decidir cualquier lenguaje recursivo y aceptar cualquier lenguaje recursivamente enumerable. De acuerdo a la tesis de Church-Turing, los problemas solucionables por una máquina universal de Turing son exactamente esos problemas solucionables por un algoritmo o un método efectivo de computación, para cualquier definición razonable de esos términos. Por estas razones, una máquina universal de Turing sirve como un estándar contra el cual comparar sistemas computacionales, y un sistema que puede simular una máquina universal de Turing es llamado Turing completo.
Una versión abstracta de la máquina universal de Turing es la función universal, una función computable que puede ser usada para calcular cualquier otra función computable. El teorema utm demuestra la existencia de dicha función.
Sin pérdida de generalidad, la entrada de la máquina de Turing puede asumirse en el alfabeto {0, 1}; cualquier otro alfabeto finito puede ser codificado sobre {0, 1}. El comportamiento de una máquina de Turing M está determinado por su función de transición. Esta función puede ser fácilmente codificada 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 puede deducirse de la tabla de la función de transición. Los distinguidos estados y símbolos pueden ser identificados por su posición, por ejemplo, los dos primeros estados pueden ser por convención los estados iniciar y parar. En consecuencia, toda máquina de Turing puede codificarse como una cadena sobre el alfabeto {0, 1}. Adicionalmente, se conviene a que toda codificación no válida se mapea 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 al rellenar la codificación con un número arbitrario de (digamos) 1 al final, al igual que trabajan los comentarios en un lenguaje de programación. No debería ser sorpresa que podemos 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-μ. Similarmente, nuestra construcción asocia a cada cadena binaria α, una máquina de Turing Mα.
A partir 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 con la entrada x en N pasos, entonces existe una máquina universal de Turing multi cinta 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 depende del tamaño del alfabeto de M, número de cintas y varios estados. Efectivamente es una simulación O(N log N).
Cuando Alan Turing vino con la idea de una máquina universal tenía en mente el más simple modelo de computación lo suficientemente poderoso como para calcular todas las posibles funciones que pueden ser calculadas. En 1956 Claude Shannon primero planteó explícitamente la cuestión de encontrar la más pequeña máquina universal de Turing posible. Él mostró que dos símbolos eran suficientes, siempre y cuando fueran usados suficiente estados (o viceversa), y que siempre era posible intercambiar estados por símbolos.
En 1962 Marvin Minsky descubrió una máquina universal de Turing de 7 estados 4 símbolos mediante sistemas 2 tag. Desde entonces han sido encontradas otras pequeñas máquinas universales de Turing por Yuri Rogozin y otros al extender este acercamiento de simulación de sistema de tag. Si denotamos por (m, n) la clase de UTMs con m estados y n símbolos, han sido encontradas las siguientes tuplas: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) y (2, 18). La máquina (4, 6) de Rogozhin usa solo 22 instrucciones, y no es conocida una UTM estándar de menor complejidad descripcional.
Sin embargo, generalizando el modelo de máquina de Turing estándar admite UTMs aún más pequeñas. 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 universalidad "parcialmente débil" o "débil", respectivamente. Máquinas universales Turing pequeñamente débiles que simulan el autómata celular regla 110 ha sido dado por los pares de estado símbolo (6, 2), (3, 3) y (2, 4). La prueba de universalidad de la máquina de Turing de 2 estados 3 símbolos de Wolfram extiende más la noción de universalidad débil al permitir ciertas configuraciones iniciales no periódicas. Otras variantes en el modelo de máquina de Turing estándar que dieron UTMs pequeñas incluyen máquinas con múltiples cintas o cintas de múltiples dimensiones y máquinas acopladas con un autómata finito.
Referencias generales
Artículos seminales
Otras referencias
Escribe un comentario o lo que quieras sobre Máquina universal de Turing (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)