Máquina de Turing universal

Para otros usos de este término, véase Turing (desambiguación).

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.

Introducción

 

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:

Es posible inventar una única máquina que puede ser usada para computar cualquier secuencia computable. Si esta máquina U es provista con una cinta en el principio de que está escrito el S.D ["Descripción estándar" de una tabla de acción] de alguna máquina de computación M, entonces U computará la misma secuencia que M.^[1]​

Computador de programa almacenado

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";^[2]​ 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.^[3]​ Knuth además afirma que

Puede decirse que la primera rutina interpretativa es la "máquina universal de Turing"... Rutinas interpretativas, en el sentido convencional, fueron mencionadas por John Mauchly en sus lecturas en la Moore School en 1946... Turing también tomó parte en este desarrollo; bajo su dirección fueron escritos sistemas interpretativos para el computador Pilot ACE"

Knuth (1973, p. 226)

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:

La teoría de funciones computables de Turing antecedió pero no ha influenciado mucho en la extensa construcción de computadoras digitales. Estos dos aspectos de la teoría y la práctica han sido desarrollados casi en su totalidad independientemente uno de la otro. Sin duda, la razón principal es que los lógicos están interesados en cuestiones radicalmente diferentes de las que les interesan a los matemáticos aplicados e ingenieros eléctricos, Sin embargo, no se puede fallar en acuñar como bastante extraño que a menudo los mismos conceptos son expresados en términos muy diferentes en los dos desarrollos

Wang 1954, 1957:63

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.

Teoría matemática

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.

Eficiencia

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).^[4]​

Máquinas más pequeñas

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).^[5]​^[6]​^[7]​ 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).^[8]​ 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

1. Boldface replacing script. Turing 1936 in Davis 1965:127-128. An example of Turing's notion of S.D is given at the end of this article.
2. Knuth, 1973, p. 225.
3. In particular: Burks, Goldstine, von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted in Bell and Newell 1971
4. Arora and Barak, 2009, Theorem 1.9
5. Rogozhin, 1996
6. Kudlek and Rogozhin, 2002
7. Neary and Woods, 2009
8. Neary and Woods, 2009b

Referencias generales

• Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach", Cambridge University Press, 2009, ISBN 978-0-521-42426-4, section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"

Artículos seminales

• F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines. JACM, 13(4):533–546, 1966.

Otras referencias

• Copeland, Jack, ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Oxford UK: Oxford University Press, ISBN 0-19-825079-7 .
• Davis, Martin (1980), «What is Computation?», en Steen, Lynn Arthur, ed., Mathematics Today: Twelve Informal Essays, New York NY: Vintage Books (Random House), ISBN 978-0-394-74503-9 ..
• Davis, Martin (2000), Engines of Logic: Mathematicians and the origin of the Computer (1st edición), New York NY: W. W. Norton & Company, ISBN 0-393-32229-7, (pb.) .
• Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4}.
• Herken, Rolf (1995), The Universal Turing Machine – A Half-Century Survey, Springer Verlag, ISBN 3-211-82637-8 .
• Knuth, Donald E. (1973) [1968]. The Art of Computer Programming Second Edition, Volume 1/Fundamental Algorithms (2 edición). Addison-Wesley Publishing Company. 
• Kudlek, Manfred; Rogozhin, Yurii (2002), «A universal Turing machine with 3 states and 9 symbols», LNCS (Springer) 2295: 311-318 .
• Minsky, Marvin (1962), «Size and Structure of Universal Turing Machines using Tag Systems, Recursive Function Theory», Proc. Symp. Pure Mathematics (Providence RI: American Mathematical Society) 5: 229-238 .
• Neary, Turlough; Woods, Damien (2009), «Four Small Universal Turing Machines», Fundamenta Informaticae 91 (1) .
• Neary, Turlough; Woods, Damien (2009b), «Small Weakly Universal Turing Machines», 17th International Symposium on Fundamentals of Computation Theory, Springer LNCS 5699, pp. 262-273 .
• Penrose, Roger (1989), The Emperor's New Mind, Oxford UK: Oxford University Press, ISBN 0-19-851973-7, (hc.), (pb.) .
• Rogozhin, Yurii (1996), «Small Universal Turing Machines», Theoretical Computer Science 168 (2): 215-240, doi:10.1016/S0304-3975(96)00077-1 .
• Shannon, Claude (1956), «A Universal Turing Machine with Two Internal States», Automata Studies, Princeton, NJ: Princeton University Press, pp. 157-165 .
• Turing, Alan (1936), «On Computable Numbers, With an Application to the Entscheidungsproblem», Proceedings of the London Mathematical Society 42 (2) . (and Turing, A.M. (1938), «On Computable Numbers, with an Application to the Entscheidungsproblem: A correction», Proceedings of the London Mathematical Society, 2 (1937) 43 (6): 544-6, doi:10.1112/plms/s2-43.6.544 .). Reprinted in Martin Davis ed. (1965) The Undecidable, Raven Press, Hewlett NY pp. 115–154; with corrections to Turing's UTM by Emil Post cf footnote 11 in Davis 1965:299.

Véase también

• Turing completo
• Máquina de Turing
• Máquina de Turing alternante

•   Datos: Q2703890