LA MÁQUINA UNIVERSAL DE TURING

Todavía no he descrito el concepto de máquina universal de Turing. No es demasiado difícil enunciar el principio que hay detrás, aunque los detalles son complicados. La idea básica consiste en codificar la lista de instrucciones para una máquina de Turing arbitraria T en una cadena de 0's v 1's que pueda ser representada en una cinta. Esta cinta se utiliza a continuación como la parte inicial del input de alguna máquina de Turing particular U —que llamaremos máquina universal de Turing— que actúa sobre el resto del input de la misma forma que lo hubiera hecho T. La máquina universal de Turing es un imitador universal. ¡La parte inicial de la cinta proporciona a la máquina U toda la información que necesita para imitar exactamente a cualquier máquina T!

Para ver cómo funciona, necesitamos en primer lugar un modo sistemático de numerar máquinas de Turing. Consideremos la lista de instrucciones que define a alguna máquina de Turing particular, por ejemplo, una de las descritas anteriormente. Debemos codificar esta lista en una cadena de 0's y 1's siguiendo un esquema preciso. Esto puede hacerse con la ayuda del procedimiento de «contracción» que adoptamos antes. En efecto, si representamos los símbolos D, I, ALTO, la flecha ( → ) y la coma, mediante los números 2, 3, 4, 5 y 6, respectivamente, podemos codificarlos como contracciones por 110, 1110, 11110, 111110 y 1111110. Entonces los dígitos 0 y 1, codificados como 0 y 10, respectivamente pueden ser utilizados en las cadenas reales de estos símbolos que aparecen en la tabla. No necesitamos una notación diferente para distinguir en la tabla de la máquina de Turing las cifras en caracteres grandes 0 y 1 de las más pequeñas, ya que la posición de los dígitos grandes en el extremo de la numeración binaria es suficiente para distinguirlos de los demás. Así, por ejemplo, 1101 se leería como el número binario 1101 y se codificaría en la cinta como 1010010. En particular, 00 se leería como 00, que puede codificarse sin ambigüedad como 0, o como un símbolo que no se haya usado. Podemos economizar mucho trabajo si no codificamos ninguna flecha ni ninguno de los símbolos que les preceden, basándonos, en cambio, en el ordenamiento numérico de las instrucciones para especificar cuáles deben ser estos símbolos, aunque para este procedimiento debemos asegurarnos de que no haya huecos en el ordenamiento, añadiendo algunas órdenes «mudas» donde sea necesario. (Por ejemplo, la máquina de Turing XN+1 no tiene ninguna orden que nos diga qué hacer con 1100 ya que esta combinación no aparece nunca en el funcionamiento de la máquina, de modo que debemos insertar una orden «muda», por ejemplo 1100 → 00D, que puede incorporarse a la lista sin cambiar nada. Análogamente deberíamos insertar 101 → 00D en la máquina XN×2). Sin estas órdenes «mudas», la codificación de las instrucciones subsiguientes sería equivocada. En realidad no necesitamos la coma al final de cada instrucción, como aparece, puesto que los símbolos I o D bastan para separar las instrucciones. En consecuencia, adoptamos sencillamente la siguiente codificación:

0 para 0 o 0, 10 para 1 o 1, 110 para D, 1110 para I, 11110 para ALTO

Como ejemplo, vamos a codificar la máquina de Turing XN+1 (con la instrucción 1100 → 00D insertada). Prescindiendo de las flechas, de los dígitos que los preceden, y de las comas, tenemos:

00D 11D 00D 101D 110I 101D 01ALTO 1000I 1011I 1001I 1100D 101D 00D 1111D 111D 1110D.

Podemos mejorar el procedimiento prescindiendo de todos los 00 y reemplazando cada 01 por un simple 1, según lo que hemos dicho antes, para obtener

D11DD101D110I101D1ALTO1000I1011I1001I1100D101DD1111D111D1110D.

Esto se codifica como la secuencia en la cinta

11010101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100110

Para simplificar un poco más, podemos también borrar siempre el 110 inicial (junto con la cinta infinita en blanco que le precede) puesto que esto significa 00D, que representa la instrucción inicial 00 → 00D que he supuesto implícitamente común a todas las máquinas de Turing —de modo que el dispositivo puede empezar a funcionar arbitrariamente lejos hacia la izquierda de las marcas sobre la cinta e ir hacia la derecha hasta llegar a la primera marca— y siempre podemos borrar el 110 final (y la implícita secuencia infinita de 0's que se supone que le sigue) ya que todas las descripciones de máquinas de Turing deben acabar de esta forma (pues todas terminan con D, I o ALTO). El número binario resultante es el número de la máquina de Turing, que en el caso de XN+1 es:

10101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100

En notación decimal estándar este número en particular es

450.813.704.461.563.958.982.113.775.643.437.908.

A veces nos referimos, de forma un tanto imprecisa, a la máquina de Turing cuyo número es n, como la n-ésima máquina de Turing, denotada por T_n.

Así, XN+1 es la 450.813.704.461.563.958.982.113.775.643.437.908-ésima máquina de Turing.

Parece un hecho sorprendente que tengamos que ir tan lejos en la «lista» de máquinas de Turing antes de encontrar la que realiza una operación tan trivial como la de sumar uno (en la notación binaria expandida) a un número natural. (No creo haber sido especialmente torpe en mi codificación, aunque sí veo posibles mejoras menores). En realidad existen algunas máquinas de Turing interesantes con números menores. Por ejemplo, UN+1 tiene el número binario

101011010111101010

que simplemente es 177.642 en notación decimal. En consecuencia, la muy trivial máquina de Turing UN+1, que coloca un 1 adicional al final de una secuencia de 1’s, es la 177.642-ésima máquina de Turing. A modo de curiosidad podemos señalar que multiplicar por dos queda en alguna parte entre estas dos en la lista de máquinas de Turing, en cualquiera de las notaciones, pues encontramos que el número de XN×2 es 10.389.728.107 mientras que el de UN×2 es 1.492.923.420.919.872.026.917.547.669.

Quizá no le sorprenda saber, en vista de la magnitud de estos números, que la inmensa mayoría de los números naturales no dan máquinas de Turing que trabajen en forma alguna. Hagamos la lista de las trece primeras máquinas de Turing, según esta numeración:

T₀: 00 → 00D, 01 → 00D,

T₁: 00 → 00D, 01 → 00I,

T₂: 00 → 00D, 01 → 01D,

T₃: 00 → 00D, 01 → 00ALTO,

T₄: 00 → 00D, 01 → 10D,

T₅: 00 → 00D, 01 → 01I,

T₆: 00 → 00D, 01 → 00D, 10 → 00D

T₇: 00 → 00D, 01 → ???,

T₈: 00 → 00D, 01 → 100D,

T₉: 00 → 00D, 01 → 10I,

T₁₀: 00 → 00D, 01 → 11D,

T₁₁: 00 → 00D, 01 → 01ALTO,

T₁₂: 00 → 00D, 01 → 00D, 10 → 00D

De éstas, T₀ simplemente se mueve hacia la derecha borrando todo lo que encuentra, sin detenerse nunca ni volver atrás. La máquina T₁ consigue finalmente el mismo efecto pero de una manera más torpe, saltando hacia atrás cada vez que borra una marca de la cinta. La máquina T₂, al igual que la T₀, también se mueve incesantemente hacia la derecha, pero es más respetuosa y deja todo tal como estaba. Ninguna de las dos sirve como máquina de Turing ya que no se detienen nunca. T₃ es la primera máquina respetable: se detiene, modestamente, después de cambiar el primer 1 (el más a la izquierda) por un 0.

T₄ tropieza con un serio problema. Una vez que encuentra su primer 1 en la cinta entra en un estado interno para el que no hay listado, de modo que no tiene instrucciones sobre lo que debe hacer a continuación. T₈, T₉ y T₁₀ tropiezan con el mismo problema. La dificultad con T₇ es aún más grave. La cadena de 0's y 1's que la codifica incluye una secuencia de cinco 1's sucesivos: 110111110. No existe interpretación para semejante secuencia, así que se quedará bloqueada en cuanto encuentre su primer 1. (Llamaré a T₇ a cualquier otra máquina T_n para la que la expresión binaria de n contenga una secuencia de más de cuatro 1's, una máquina no especificada correctamente). Las máquinas T₅, T₆ y T₁₂ tropiezan con problemas similares a los de T₀, T_l o T₂. Sencillamente continúan indefinidamente sin detenerse nunca. ¡Todas las máquinas T₀, T₁, T₂, T₄, T₅, T₆, T₇, T₈, T₉, T₁₀ y T₁₂ son inútiles! Sólo T₃ y T₁₁ son máquinas de Turing que funcionan, y no muy interesantes por cierto. T₁₁ es aún más modesta que T₃: se detiene al primer encuentro con un 1 y no cambia nada.

Señalemos que hay también una redundancia en nuestra lista. La máquina T₁₂ es idéntica a T₆, y también idéntica en actuación a T₀, puesto que el estado interno 1 de T₆ y T₁₂ nunca interviene. No tenemos que preocuparnos por esta redundancia ni por la proliferación de máquinas de Turing inútiles en la lista. Sería desde luego posible mejorar nuestra codificación para que se eliminaran muchas de las máquinas inútiles y se redujera considerablemente la redundancia. Todo esto se haría a expensas de la simplicidad de nuestra pobre máquina universal de Turing que tiene que descifrar el código y tratar de ser la máquina de Turing T_n cuyo número n está leyendo. Tal vez merecería la pena hacerlo si pudiéramos eliminar todas las máquinas inútiles (o todas las redundancias). Pero, como veremos en un momento, ¡esto no es posible! Por consiguiente, dejemos nuestra codificación como está. Será conveniente interpretar una cinta con su serie de marcas, v.g.

…0001101110010000…

como la representación binaria de algún número. Recordemos que los 0’s continúan indefinidamente en ambas direcciones, pero que hay sólo un número finito de l’s. Estoy suponiendo también que el número de 1’s es distinto de cero (esto es, hay al menos un 1). Podríamos decidir leer la cadena finita de símbolos entre el primer y el último 1 (inclusive), que en el caso anterior es

110111001,

como la notación binaria de un número natural (aquí 441, en notación decimal). Sin embargo, este procedimiento sólo nos daría números impares (números cuya notación binaria termina con un 1) y pretendemos representar todos los números naturales. En consecuencia, adoptamos el sencillo expediente de eliminar el 1 final (que se toma como un simple marcador que señala la terminación de la expresión) y leer lo que queda como un número binario.^[2.8] Así, para el ejemplo anterior, tenemos el número binario

11011100,

que en notación decimal es 220. Este método tiene la ventaja de que el cero también está representado como una cinta marcada, a saber

…0000001000000…

Consideremos la acción de la máquina de Turing T_n sobre alguna cadena (finita) de 0’s y 1’s en una cinta que introducimos por la derecha. Será conveniente considerar también esta cinta como la representación binaria de algún número, digamos m, según el esquema dado más arriba. Supongamos que tras una serie de pasos la máquina T_n finalmente se detiene (es decir, llega a ALTO). La cadena de dígitos binarios que la máquina ha producido a la izquierda es la respuesta al cálculo. La leemos también como la representación binaria de un número, digamos p. Escribiremos esta relación, que expresa el hecho de que cuando la n-ésima máquina de Turing actúa sobre m produce p, como:

T_n(m) = p.

Consideremos ahora esta relación en una forma ligeramente diferente. Imaginemos que expresa una operación particular que se aplica al par de números n y m para dar lugar al número p. (Así, dados los dos números n y m podemos calcular a partir de ellos p, viendo lo que la n-ésima máquina de Turing hace con m). Esta operación particular es un procedimiento totalmente algorítmico y, por lo tanto, puede ser llevado a cabo por una máquina de Turing U; esto es, U actúa sobre el par (n,m) para producir p. Puesto que la máquina de Turing tiene que actuar sobre ambos, n y m, para producir el resultado simple p, necesitaremos algún modo de codificar el par (n,m) en la cinta única. Para esto podemos suponer que n está escrito en la notación binaria ordinaria y que termina con la secuencia 111110. (Recordemos que el número binario de toda máquina de Turing correctamente especificada es una secuencia formada sólo a base de 0's, 10's, 110's, 1110's y 11110's, y por consiguiente no contiene ninguna secuencia de más de cuatro 1’s. De modo que si T_n es una máquina correctamente especificada, la aparición de 111110 significa verdaderamente que la descripción del número n ha terminado). Todo lo que hay a continuación es simplemente la cinta, representada por m de acuerdo con nuestra prescripción anterior (es decir, el número binario m seguido inmediatamente de 1000…). Entonces esta segunda parte es sencillamente la cinta sobre la que se supone que actúa T_n. A modo de ejemplo, si tomamos n = 11 y m = 6 tenemos que la cinta sobre la que U tiene que actuar posee la secuencia de marcas

…000101111111011010000…

Ésta está formada por:

…0000 (cinta en blanco inicial)

1011 (representación binaria de 11)

111110 (termina n)

110 (representación binaria de 6)

10000… (resto de la cinta)

Lo que tendría que hacer la máquina de Turing U, en cada paso de la operación de T_n sobre m, sería examinar la estructura de la serie de dígitos en la expresión de n de modo que pueda hacerse la sustitución apropiada de los dígitos de m (esto es, la «cinta» de T_n). De hecho, no es difícil (aunque sí tedioso) ver cómo se podría construir realmente una máquina semejante. Su propia lista de instrucciones nos estaría proporcionando un medio de leer la entrada apropiada en dicha «lista», entrada que está codificada en el número n, en cada paso de la aplicación a los dígitos de la «cinta», tal como figuran en m. Por supuesto que habría una serie de idas y vueltas, atrás y adelante de los dígitos de m a los de n y viceversa, y el procedimiento se haría desesperadamente lento. De todas formas, puede darse sin duda una lista de instrucciones para una máquina semejante; y llamamos a esa máquina una máquina universal de Turing. Al indicar la acción de esta máquina sobre el par de números n y m por U(n,m), tenemos:

U(n,m) = T_n(m)

para cada (n,m) para el que T_n es una máquina de Turing correctamente especificada.^[2.9] La máquina U, cuando se alimenta inicialmente con el número n, imita exactamente a la n-ésima máquina de Turing.

Puesto que U es una máquina de Turing, tendrá también un número; es decir, tendremos

U=T_u,

para algún número u. ¿Qué tan grande es u? De hecho podemos tomar exactamente

u=72448553353393175771983950396157112379523606725565 59631108144796606505059404241090310483613632359365 64444345838222688327876762655614469281411771501784 25517075540856576897533463569424784885970469347257 39988582283827795294683460521061169835945938791885 54632644092552550582055598945189071653741489603309 67530204315536250349845298323206515830476641421307 08819329717234151056980262734686429921838172157333 48282307345371342147505974034518437235959309064002 43210773421788514927607975976344151230795863963544 92269159479654614711345700145048167337562172573464 52273105448298078496512698878896456976090663420447 79890219144379328300194935709639217039048332708825 96201301773727202718625919914428275437422351355675 13408422229988937441053430547104436869587640517812 80194375308138706399427728231564252892375145654438 99052780793241144826142357286193118332610656122755 53181020751108533763380603108236167504563585216421 48695423471874264375444287900624858270912404220765 38754264454133451748566291574299909502623009733738 13772416217274772361020678685400289356608569682262 01419824862169890260913094029857060017430067008689 67590344734174127874255812015493663938996905817738 59165405535670409282133222163141097871081459978669 59970450968184190629944365601514549048809220844800 34822492077304030431884298993931352668823496621019 47161910701461968523192847482034495897709553561107 02758174873332729667899879847328409819076485127263 10017401667873634776058572450369644348979920344899 97455662402937487668839751404451665707750060513883 99166881407254554466522205072426239237921152531816 25125363050931728631422004064571305275802307665183 351995689139748137504926429605010013651980186945639498

(o alguna otra posibilidad por lo menos de este orden de magnitud). Sin duda, este número parece escalofriante y en efecto es escalofriante, pero no veo cómo reducirlo significativamente. Los procedimientos de codificación y las especificaciones que he dado para máquinas de Turing son bastante razonables y simples pero, a pesar de todo, hemos llegado inevitablemente a este enorme número para la codificación de una máquina universal de Turing real.^[2.10]

He dicho que todas las computadoras modernas de tipo general son en efecto, máquinas universales de Turing. No quiero decir que el diseño lógico de estos ordenadores necesite parecerse mucho a la descripción de una máquina universal de Turing que acabo de dar. Lo importante es simplemente que, si antes que nada suministramos a cualquier máquina universal de Turing un programa apropiado (la parte inicial de la cinta input), ¡podemos hacer que imite el comportamiento de cualquier máquina de Turing! En la descripción anterior, el programa toma la forma

10101001101010100101001011010101001101001001010111 01001101001000001011010001010101000111010010000101 01101000000100110100100010010111010010000110101000 00100101110100100101001101001001010101101001101001 00101001011010011010010100000101101001000001110101 00100110101010100001011101001010000101110100101010 10111010100010010110100100111010010101000101110100 01001110101000010110100100111010010101010101110100 10001110100101010100101110100100011101010000010101 01110011010100000101101001001110101000000101110100 10110101000001010110100101001011101010000100101110 10000110101000100001011010100110101000100010110101 01010010111010100010100101101000101010101110100100 00101011010100010111010100100101010111010101001001 01110101000111010100011101010010010010111010100011 10101001010001011101010001011101010000100101110101 00011101000101000101110100101001011101010010101001 01110100101010101010110101000010101010110100001001 11010000101010101011101010100010101110101010001010 11101000000111010101000100101110100000011101010100 10001011101010000001101010000101101000000111010010 00000101110101000111010100100010101110101001101010 10100010101101000001101010101001010101101000000100 11010101010010011101010011010101010010010110101001 10100100100111010000011010101010100101011010100010 01101000101001010101110100000110101010101010010110 10001000111010001010101010101101000100011101000010 10111010001001000011101001101000000010011101000000 10010111010001000101001110100000010010111010010101 01010010110100001010101011101000100101001011101000 00100010111010101001011010001000100111010000010010 10111010000001010101101000010001110011110100001000 00111010000100100111010000010100101110100000101001 01101000010001010111010000100010011010001000011101 01111010000100100101110100001001001011101000000010 10111010000101010001101000100101110100001000001110 10000100111010001000001011101010100101101000100000 10111010000101010101110100000010101011101000100001 01011101000100001010111010010000011101010010010011 01000000101011101000100010010111010101000011101010 01010110100101010100001101000001010011010000000111 01000001001001110100101101001000101001011010101001 10100010100100101101010100110100010101000101100110 10100100101110101010011010001010101010110011010100 0101010110011010010001010

de un simple número (el número n), pero hay otros procedimientos posibles y muchas variaciones sobre la forma original de Turing. De hecho, en mi propia descripción me he desviado algo de la que dio Turing originalmente, sin embargo, ninguna de estas diferencias es importante para nuestras actuales necesidades.