Máquina de Turing universal

En informática , una máquina de Turing universal ( MTU ) es una máquina de Turing capaz de calcular cualquier secuencia computable, ^{[ 1 ]} como la describió Alan Turing en su artículo fundamental "Sobre los números computables, con una aplicación al problema de decisión ". En otras palabras, una máquina de Turing capaz de simular cualquier otra máquina de Turing especializada.

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 ser humano en el proceso de calcular un número real con una máquina que solo es capaz de un número finito de condiciones .${\displaystyle q_{1},q_{2},\dots ,q_{R}}$⁠ ; que se denominarán " m- configuraciones". ^{[ 2 ]} A continuación, describió el funcionamiento de dicha máquina, como se describe más adelante, y argumentó:

Sostengo que estas operaciones incluyen todas aquellas que se utilizan en el cálculo de un número. ^{[ 3 ]}

Turing introdujo la idea de una máquina de este tipo entre 1936 y 1937.

Martin Davis argumenta de forma convincente que la concepción de Turing de lo que hoy se conoce como "la computadora de programa almacenado", al colocar la "tabla de acciones" —las instrucciones para la máquina— en la misma "memoria" que los datos de entrada, influyó notablemente en la concepción de John von Neumann de la primera computadora estadounidense de símbolos discretos (a diferencia de las analógicas): la EDVAC . Davis cita a la revista Time al respecto, afirmando que "todo aquel que teclea  ... está 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 argumenta que la computadora Automatic Computing Engine (ACE) de Turing "anticipó" las nociones de microprogramación ( microcódigo ) y procesadores RISC . ^{[ 5 ]} Donald Knuth cita el trabajo de Turing en la computadora 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 que hizo Turing de una "pila" de hardware. ^{[ 7 ]}

Así como la máquina de Turing impulsaba 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 y brillante programador" para el EDVAC. ^{[ 8 ]} El "primer programa serio" de Von Neumann... [consistía] simplemente en ordenar datos de manera eficiente. ^{[ 9 ]} Knuth observa que el retorno de la subrutina integrado en el propio programa 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 es la "Máquina de Turing Universal"... 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 se escribieron 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, 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 puede calcularse mecánicamente. Por ejemplo, el problema de determinar si una máquina de Turing arbitraria se detendrá con una entrada particular o con todas las entradas, conocido como el problema de la parada , demostró ser, en general, indecidible en el artículo original de Turing. El teorema de Rice demuestra 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 precisamente aquellos que puede resolver un algoritmo o un método de computación eficaz , para cualquier definición razonable de estos términos. Por estas razones, una máquina de Turing universal sirve como estándar para comparar sistemas computacionales, y un sistema que puede simular una máquina de Turing universal se denomina 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 UTM demuestra la existencia de dicha función.

Sin pérdida de generalidad, se puede asumir que la entrada de una 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 pueden deducirse de la tabla de la función 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 parada. En consecuencia, toda máquina de Turing puede codificarse como una cadena sobre el alfabeto {0, 1}. Además, concluimos que toda codificación inválida se corresponde con una máquina de Turing trivial que se detiene inmediatamente, y que toda 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 sorprendernos 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 en 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 , el número de cintas y el número de estados. Efectivamente, esto es una${\displaystyle {\mathcal {O}}\left(N\log {N}\right)}$simulación, utilizando 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${\displaystyle {\mathcal {O}}(N)}$simulación. ^{[ 13 ]}

Cuando Alan Turing concibió la idea de una máquina universal, tenía en mente el modelo de computación más simple, lo suficientemente potente como para calcular todas las funciones posibles. 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 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 utilizando sistemas de 2 etiquetas . Otras pequeñas máquinas de Turing universales han sido encontradas desde entonces por Yurii Rogozhin y otros 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 utiliza 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 estas generalizaciones consiste en 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 presentado 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 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 en una máquina de Turing se permiten múltiples cabezales leyendo posiciones sucesivas de la cinta, no se requieren estados internos, ya que estos pueden codificarse en la cinta. Por ejemplo, consideremos una cinta con 6 colores: 0, 1, 2, 0A, 1A, 2A. Consideremos una cinta como 0,0,1,2,2A,0,2,1, donde una máquina de Turing de 3 cabezales se sitúa sobre la tripleta (2,2A,0). Las reglas convierten cualquier tripleta en otra y mueven los 3 cabezales hacia la izquierda o hacia la derecha. Por ejemplo, las reglas podrían convertir (2,2A,0) en (2,1,0) y mover el cabezal 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 por ninguna letra). El caso de una máquina de Turing de 2 cabezales es muy similar. Por lo tanto, una máquina de Turing de 2 cabezales sin estados internos puede ser universal con 6 colores. Se desconoce cuál es el número mínimo de colores necesarios para una máquina de Turing multicabezal, o si es posible una máquina de Turing universal de dos colores sin estados internos con múltiples cabezales. Esto también implica 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 un cabezal que muestrea una letra y sus ocho vecinos, solo se necesitan dos colores, ya que, por ejemplo, un color puede codificarse en un patrón triple vertical como el 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 quienes deseen asumir el reto de diseñar una UTM exactamente como la especificó Turing, consulten el artículo de Davies en Copeland (2004) . Davies corrige los errores del original y muestra cómo se vería una ejecución de ejemplo. Logró realizar con éxito una simulación (algo simplificada).

El siguiente ejemplo está tomado de Turing (1937) . Para 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 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 sin cambios.

Después de codificar cada 5-tupla, esta 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 está separado por ";", es decir:

Este código lo colocó en casillas alternas —las "casillas F"— dejando vacías las "casillas E" (las que se borran). 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 casillas alternas y, por último, el símbolo de dos puntos dobles " :: " (los espacios en blanco se muestran aquí con "." para mayor claridad):

La tabla de acciones (tabla de transición de estados) de la máquina U se encarga de decodificar los símbolos. La tabla de acciones de Turing registra su posición con los marcadores "u", "v", "x", "y" 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 ";" y " x" mantiene la posición con respecto a la configuración DAA "m" actual . La tabla de acciones de la máquina U reorganiza estos símbolos (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 proporciona 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 su código completo de la máquina U. Afirma que realmente se trata de 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 una UTM multitape definida mediante la composición de máquinas elementales con semántica muy simple, en lugar de proporcionar explícitamente su tabla de acciones completa. Este enfoque fue suficientemente modular como para permitirles demostrar formalmente la corrección de la máquina en el asistente de pruebas Matita . ^{[ 20 ]}

• Máquina de Turing alternante : modelo de computación abstracto 
• Máquina contadora : máquina abstracta utilizada en lógica formal y en informática teórica. 
• Predicado T de Kleene : concepto en la teoría de la computabilidad. 
• Marca y espacio : estados de una señal de comunicaciones 
• Equivalentes de máquinas de Turing : dispositivos informáticos hipotéticos 
• Constructor universal de Von Neumann : autómata celular autorreplicante 

• Smith, Alvy Ray. "Una máquina de Turing universal de tarjetas de visita" (PDF) . Consultado el 2 de enero de 2020 .