La prueba de Turing es una prueba de Alan Turing , publicada por primera vez en noviembre de 1936 [1] con el título " Sobre los números computables, con una aplicación al problema de entscheidung ". Fue la segunda prueba (después del teorema de Church ) de la negación del problema de entscheidung de Hilbert ; es decir, la conjetura de que algunas preguntas puramente matemáticas de sí o no nunca pueden ser respondidas por cálculo; más técnicamente, que algunos problemas de decisión son " indecidibles " en el sentido de que no hay un algoritmo único que dé infaliblemente una respuesta correcta de "sí" o "no" a cada instancia del problema. En las propias palabras de Turing: "lo que probaré es bastante diferente de los resultados bien conocidos de Gödel... Ahora demostraré que no hay un método general que diga si una fórmula dada U es demostrable en K [ Principia Mathematica ]". [2]
Turing siguió esta prueba con otras dos. La segunda y la tercera se basan en la primera. Todas se basan en su desarrollo de "máquinas de computación" similares a máquinas de escribir que obedecen a un conjunto simple de reglas y en su posterior desarrollo de una "máquina de computación universal".
En su prueba de que el problema de Entscheidung no puede tener solución, Turing partió de dos pruebas que condujeron a su prueba final. Su primer teorema es el más relevante para el problema de la detención , el segundo es más relevante para el teorema de Rice .
Primera prueba : que no existe ninguna "máquina de computación" que pueda decidir si una "máquina de computación" arbitraria (representada por un entero 1, 2, 3, . . .) está o no "libre de círculos" (es decir, continúa imprimiendo su número en binario ad infinitum): "... no tenemos un proceso general para hacer esto en un número finito de pasos" (p. 132, ibid .). La prueba de Turing, aunque parece utilizar el "proceso diagonal", de hecho muestra que su máquina (llamada H) no puede calcular su propio número, y mucho menos el número diagonal completo ( argumento diagonal de Cantor ): "La falacia en el argumento reside en la suposición de que B [el número diagonal] es computable" [3] La prueba no requiere muchas matemáticas.
Segunda prueba : Esta es quizás más familiar para los lectores como el teorema de Rice : "Podemos demostrar además que no puede haber ninguna máquina E que, cuando se le suministra el SD ["programa"] de una máquina arbitraria M, determine si M alguna vez imprime un símbolo dado (digamos 0) " [a]
Tercera prueba : "Para cada máquina de computación M construimos una fórmula Un(M) y mostramos que, si hay un método general para determinar si Un(M) es demostrable, entonces hay un método general para determinar si M alguna vez imprime 0". [2]
La tercera prueba requiere el uso de la lógica formal para demostrar un primer lema, seguido de una breve prueba verbal del segundo:
Lema 1: Si S1 [símbolo "0"] aparece en la cinta en alguna configuración completa de M, entonces Un(M) es demostrable. [4]
Lema 2: [Recíproco] Si Un(M) es demostrable, entonces S1 [símbolo "0"] aparece en la cinta en alguna configuración completa de M. [5]
Finalmente, en sólo 64 palabras y símbolos, Turing demuestra por reductio ad absurdum que "el problema de la solución de Hilbert no puede tener solución". [2]
Turing creó una maraña de abreviaturas. Consulte el glosario al final del artículo para ver las definiciones.
Algunas aclaraciones clave:
La máquina H de Turing está intentando imprimir un número diagonal de 0 y 1.
Este número diagonal se crea cuando H realmente "simula" cada máquina "exitosa" bajo evaluación e imprime la "cifra" R-ésima (1 o 0) de la máquina "exitosa" R-ésima.
Turing dedicó gran parte de su artículo a "construir" sus máquinas para convencernos de su veracidad, algo que exigía su utilización de la forma de prueba reductio ad absurdum . Debemos destacar la naturaleza "constructiva" de esta prueba. Turing describe lo que podría ser una máquina real, realmente construible. El único elemento cuestionable es la existencia de la máquina D, que esta prueba acabará demostrando que es imposible.
Turing comienza la prueba con la afirmación de la existencia de una máquina de “decisión/determinación” D. Cuando se le introduce cualquier SD (cadena de símbolos A, C, D, L, R, N, punto y coma “;”), determinará si esta SD (cadena de símbolos) representa una “máquina de computación” que es “circular” —y por lo tanto “insatisfactoria u”— o “libre de círculos” —y por lo tanto “satisfactoria s”.
Turing ha demostrado previamente en su comentario que todas las "máquinas de computación" (máquinas que calculan un número como 1 y 0 para siempre) pueden escribirse como una SD en la cinta de la "máquina universal" U. La mayor parte de su trabajo previo a su primera prueba se dedica a demostrar que realmente existe una máquina universal, es decir,
Realmente existe una máquina universal U
Para cada número N, realmente existe una DE única,
Cada máquina de Turing tiene una SD
Cada SD en la cinta de U puede ser “ejecutada” por U y producirá la misma “salida” (figuras 1, 0) que la máquina original.
Turing no hace ningún comentario sobre cómo la máquina D lleva a cabo su trabajo. Por el bien del argumento, suponemos que D primero comprobaría si la cadena de símbolos está "bien formada" (es decir, en forma de algoritmo y no simplemente de un revoltijo de símbolos), y si no lo está, la descartaría. Luego iría a "cazar círculos". Para ello, tal vez utilizaría "heurísticas" (trucos: enseñados o aprendidos). A los efectos de la prueba, estos detalles no son importantes.
Turing describe entonces (de manera bastante vaga) el algoritmo (método) que debe seguir una máquina que él llama H. La máquina H contiene en su interior la máquina de decisiones D (por lo tanto, D es una “subrutina” de H). El algoritmo de la máquina H se expresa en la tabla de instrucciones de H, o tal vez en la Descripción estándar de H en cinta y unida a la máquina universal U; Turing no lo especifica.
Al describir la máquina universal U, Turing ha demostrado que la SD de una máquina (una cadena de letras similar a un “programa”) se puede convertir en un entero (base 8) y viceversa. Cualquier número N (en base 8) se puede convertir en una SD con las siguientes sustituciones: 1 por A, 2 por C, 3 por D, 4 por L, 5 por R, 6 por N, 7 por punto y coma ";".
Resulta que el número único (DN) de la máquina H es el número "K". Podemos inferir que K es un número muy largo, tal vez de decenas de miles de dígitos. Pero esto no es importante para lo que sigue.
La máquina H es responsable de convertir cualquier número N en una cadena de símbolos SD equivalente para que la submáquina D la pruebe. (En lenguaje de programación: H pasa una "SD" arbitraria a D, y D devuelve "satisfactorio" o "insatisfactorio"). La máquina H también es responsable de mantener un recuento R ("¿Registro"?) de números exitosos (suponemos que el número de SD "exitosas", es decir, R, es mucho menor que el número de SD probadas, es decir, N). Finalmente, H imprime en una sección de su cinta un número diagonal "beta-prime" B'. H crea este B' "simulando" (en el sentido informático) los "movimientos" de cada máquina/número "satisfactorio"; eventualmente, esta máquina/número bajo prueba llegará a su "cifra" Rth (1 o 0), y H lo imprimirá. H luego es responsable de "limpiar el desorden" dejado por la simulación, incrementando N y procediendo hacia adelante con sus pruebas, ad infinitum .
Nota: Todas estas máquinas que H está buscando son lo que Turing llamó "máquinas de computación". Estas calculan números binarios decimales en un flujo infinito de lo que Turing llamó "cifras": solo los símbolos 1 y 0.
Un ejemplo: supongamos que la máquina H ha probado 13472 números y ha producido 5 números satisfactorios, es decir, H ha convertido los números del 1 al 13472 en SD (cadenas de símbolos) y se los ha pasado a D para que los pruebe. Como consecuencia, H ha contado 5 números satisfactorios y ha ejecutado el primero hasta su primera "cifra", el segundo hasta su segunda cifra, el tercero hasta su tercera cifra, el cuarto hasta su cuarta cifra y el quinto hasta su quinta cifra. El recuento ahora está en N = 13472, R = 5 y B' = ".10011" (por ejemplo). H limpia el desorden en su cinta y procede:
H incrementa N = 13473 y convierte "13473" en la cadena de símbolos ADRLD. Si la submáquina D considera que ADLRD no es satisfactoria, entonces H deja el registro de conteo R en 5. H incrementará el número N a 13474 y seguirá adelante. Por otro lado, si D considera que ADRLD es satisfactoria, entonces H incrementará R a 6. H convertirá N (de nuevo) en ADLRD [esto es solo un ejemplo, ADLRD probablemente sea inútil] y lo "ejecutará" utilizando la máquina universal U hasta que esta máquina bajo prueba (U "ejecutando" ADRLD) imprima su sexta "cifra", es decir, 1 o 0. H imprimirá este sexto número (por ejemplo, "0") en la región de "salida" de su cinta (por ejemplo, B' = ".100110").
H limpia el desorden y luego incrementa el número N a 13474.
Todo el proceso se desenreda cuando H llega a su propio número K. Continuaremos con nuestro ejemplo. Supongamos que el recuento/registro exitoso R es 12. H llega finalmente a su propio número menos 1, es decir, N = K-1 = 4335...321 4 , y este número no es exitoso. Entonces H incrementa N para producir K = 4355...321 5 , es decir, su propio número. H convierte esto en “LDDR...DCAR” y lo pasa a la máquina de decisión D. La máquina de decisión D debe devolver “satisfactorio” (es decir: H debe, por definición, continuar probando, ad infinitum , porque está “libre de círculos”). Entonces H ahora incrementa el recuento R de 12 a 13 y luego vuelve a convertir el número bajo prueba K en su SD y usa U para simularlo. Pero esto significa que H estará simulando sus propios movimientos. ¿Qué es lo primero que hará la simulación? Esta simulación K-aka-H crea una nueva N o “restablece” la “vieja” N a 1. Esta “K-aka-H” crea una nueva R o “restablece” la “vieja” R a 0. La vieja-H “ejecuta” la nueva “K-aka-H” hasta que llega a su duodécima cifra.
Pero nunca llega a la cifra 13; K-aka-H finalmente llega a 4355...321 5 , de nuevo, y K-aka-H debe repetir la prueba. K-aka-H nunca llegará a la cifra 13. La máquina H probablemente sólo imprime copias de sí misma ad infinitum en una cinta en blanco. Pero esto contradice la premisa de que H es una máquina de computación satisfactoria, no circular, que continúa imprimiendo los 1 y 0 de los números diagonales para siempre. (Veremos lo mismo si N se restablece a 1 y R se restablece a 0).
Si el lector no lo cree, puede escribir un "stub" para la máquina de decisión D (el stub "D" devolverá "satisfactorio") y luego ver por sí mismo lo que sucede en el instante en que la máquina H encuentra su propio número.
Con menos de una página, el paso de las premisas a la conclusión es oscuro.
Turing procede por reductio ad absurdum . Afirma la existencia de una máquina E, que cuando se le da la SD (Descripción estándar, es decir, "programa") de una máquina arbitraria M, determinará si M alguna vez imprime un símbolo dado (digamos 0). No afirma que esta M sea una "máquina de computación".
Dada la existencia de la máquina E, Turing procede de la siguiente manera:
La dificultad de la prueba está en el paso 1. El lector se verá ayudado por el hecho de que Turing no está explicando su sutil obra (en pocas palabras: está utilizando ciertas equivalencias entre los operadores “existenciales” y “universales” junto con sus expresiones equivalentes escritas con operadores lógicos).
He aquí un ejemplo: supongamos que vemos ante nosotros un aparcamiento lleno de cientos de coches. Decidimos recorrerlo en busca de: “Coches con neumáticos pinchados (en mal estado)”. Después de una hora aproximadamente hemos encontrado dos “coches con neumáticos en mal estado”. Ahora podemos decir con certeza que “Algunos coches tienen neumáticos en mal estado”. O podríamos decir: “No es cierto que 'Todos los coches tienen neumáticos en buen estado'”. O: “Es cierto que: 'no todos los coches tienen neumáticos en buen estado”. Vayamos a otro aparcamiento. Aquí descubrimos que “Todos los coches tienen neumáticos en buen estado”. Podríamos decir: “No hay ni un solo caso de un coche que tenga un neumático en mal estado”. Así vemos que, si podemos decir algo sobre cada coche por separado, entonces podemos decir algo sobre TODOS ellos colectivamente.
Esto es lo que hace Turing: a partir de M crea una colección de máquinas { M 1, M 2, M 3, M 4, ..., Mn } y sobre cada una escribe una frase: “ X imprime al menos un 0” y permite sólo dos “ valores de verdad ”, Verdadero = espacio en blanco o Falso = :0:. Uno por uno determina el valor de verdad de la frase para cada máquina y crea una cadena de espacios en blanco o :0:, o alguna combinación de estos. Podríamos obtener algo como esto: “ M 1 imprime un 0” = Verdadero Y “ M 2 imprime un 0” = Verdadero Y “ M 3 imprime un 0” = Verdadero Y “ M 4 imprime un 0” = Falso, ... Y “ Mn imprime un 0” = Falso. Obtiene la cadena
BBB:0::0::0: ... :0: ... hasta el infinito
Si hay un número infinito de máquinas Mn . Si por el contrario, si cada máquina hubiera producido un "Verdadero", entonces la expresión en la cinta sería
BBBBB....BBBB... hasta el infinito
De este modo, Turing ha convertido las afirmaciones sobre cada máquina considerada por separado en una única "afirmación" (cadena) sobre todas ellas. Dada la máquina (a la que llama G) que creó esta expresión, puede probarla con su máquina E y determinar si alguna vez produce un 0. En nuestro primer ejemplo anterior vemos que, en efecto, lo hace, por lo que sabemos que no todas las M de nuestra secuencia imprimen 0. Pero el segundo ejemplo muestra que, dado que la cadena está formada por espacios en blanco, cada Mn de nuestra secuencia ha producido un 0.
Lo único que le queda a Turing es crear un proceso para crear la secuencia de Mn a partir de una única M.
Supongamos que M imprime este patrón:
Turing crea otra máquina F que toma M y genera una secuencia de Mn que sucesivamente convierte los primeros n 0 en “0-barra” ( 0 ):
Afirma, sin dar detalles, que esta máquina F es realmente construible. Podemos ver que pueden pasar dos cosas: F puede quedarse sin máquinas que tengan ceros o puede tener que seguir creando máquinas hasta el infinito para “cancelar los ceros”.
Turing ahora combina las máquinas E y F en una máquina compuesta G. G comienza con la M original, luego usa F para crear todas las máquinas sucesoras M1, M2,. . ., Mn. Luego G usa E para probar cada máquina comenzando con M. Si E detecta que una máquina nunca imprime un cero, G imprime :0: para esa máquina. Si E detecta que una máquina imprime un 0 (suponemos, Turing no lo dice) entonces G imprime :: o simplemente se salta esta entrada, dejando los cuadrados en blanco. Podemos ver que pueden suceder un par de cosas.
G no imprimirá ningún 0, nunca, si todos los Mn imprimen 0, O,
G imprimirá 0 hasta el infinito si todos los M no imprimen 0, O,
G imprimirá 0 por un tiempo y luego se detendrá.
Ahora bien, ¿qué sucede cuando aplicamos E a G mismo?
Si E(G) determina que G nunca imprime un 0, entonces sabemos que todos los Mn han impreso 0. Y esto significa que, debido a que todos los Mn provienen de M, M mismo imprime 0 ad infinitum , O
si E(G) determina que G sí imprime un 0, entonces sabemos que no todos los Mn imprimen 0; por lo tanto, M no imprime 0 ad infinitum .
Podemos aplicar el mismo proceso para determinar si M imprime 1 infinitamente. Cuando combinamos estos procesos, podemos determinar si M imprime o no 1 y 0 hasta el infinito . Por lo tanto, tenemos un método para determinar si M no tiene círculos. Según la prueba 1, esto es imposible. Por lo tanto, la primera afirmación de que E existe es incorrecta: E no existe.
Aquí Turing demuestra "que el problema de la solución de Hilbert no puede tener solución". [2] Aquí
…muestra que no puede haber un proceso general para determinar si una fórmula dada U del cálculo funcional K es demostrable. ( ibíd .)
Tanto el lema n.° 1 como el n.° 2 son necesarios para formar el "SI Y SÓLO SI" necesario (es decir, la equivalencia lógica ) requerida por la prueba:
Un conjunto E es computablemente decidible si y sólo si tanto E como su complemento son computablemente enumerables (Franzén, p. 67)
Turing demuestra la existencia de una fórmula Un (M) que dice, en efecto, que "en alguna configuración completa de M, aparece 0 en la cinta" (p. 146). Esta fórmula es VERDADERA, es decir, es "construible", y muestra cómo hacerlo.
Luego Turing prueba dos lemas, el primero de los cuales requiere todo el trabajo duro (el segundo es el inverso del primero). Luego utiliza el reductio ad absurdum para demostrar su resultado final:
[Si los lectores tienen intención de estudiar la prueba en detalle, deben corregir sus copias de las páginas de la tercera prueba con las correcciones que proporcionó Turing. Los lectores también deben venir equipados con una sólida formación en (i) lógica y (ii) el artículo de Kurt Gödel : " Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas relacionados ". [b] Para obtener ayuda con el artículo de Gödel, pueden consultar, por ejemplo, a Ernest Nagel y James R. Newman , Gödel's Proof , New York University Press, 1958.]
Para seguir los detalles técnicos, el lector necesitará comprender la definición de "demostrable" y estar al tanto de "pistas" importantes.
"Demostrable" significa, en el sentido de Gödel, que (i) el sistema de axiomas en sí mismo es lo suficientemente poderoso para producir (expresar) la oración "Esta oración es demostrable", y (ii) que en cualquier prueba arbitraria "bien formada" los símbolos conducen por axiomas, definiciones y sustitución a los símbolos de la conclusión.
Primera pista: "Pongamos la descripción de M en la primera forma estándar de §6". La sección 6 describe la "codificación" muy específica de la máquina M en la cinta de una "máquina universal" U. Esto requiere que el lector conozca algunas idiosincrasias de la máquina universal U de Turing y el esquema de codificación.
(i) La máquina universal es un conjunto de instrucciones "universales" que residen en una "tabla de instrucciones". Aparte de esto, en la cinta de U, residirá una "máquina de computación" M como "código M". La tabla universal de instrucciones puede imprimir en la cinta los símbolos A, C, D, 0, 1, u, v, w, x, y, z, : . Las diversas máquinas M pueden imprimir estos símbolos solo indirectamente, ordenándole a U que los imprima.
(ii) El "código de máquina" de M consiste en sólo unas pocas letras y el punto y coma, es decir, D, C, A, R, L, N, ; . En ningún lugar dentro del "código" de M aparecerán las "cifras" numéricas (símbolos) 1 y 0. Si M quiere que U imprima un símbolo de la colección en blanco, 0, 1 , entonces utiliza uno de los siguientes códigos para indicarle a U que los imprima. Para hacer las cosas más confusas, Turing llama a estos símbolos S0, S1 y S2, es decir,
(iii) Una "máquina de computación", ya sea incorporada directamente en una tabla (como lo muestran sus primeros ejemplos), o como código de máquina M en la cinta de la máquina universal U, imprime su número en una cinta en blanco (a la derecha del código M, si lo hay) como 1 y 0 que avanzan eternamente hacia la derecha.
(iv) Si una "máquina de computación" es U+"código M", entonces el "código M" aparece primero en la cinta; la cinta tiene un extremo izquierdo y el "código M" comienza allí y continúa hacia la derecha en cuadrados alternos. Cuando el código M llega a su fin (y debe hacerlo, debido a la suposición de que estos códigos M son algoritmos finitos), las "figuras" comenzarán como 1 y 0 en cuadrados alternos, y continuarán hacia la derecha para siempre. Turing usa los cuadrados alternos (en blanco) (llamados cuadrados "E"- "borrables") para ayudar a U+"código M" a llevar un registro de dónde están los cálculos, tanto en el código M como en las "figuras" que la máquina está imprimiendo.
(v) Una "configuración completa" es una impresión de todos los símbolos en la cinta, incluyendo el código M y las "figuras" hasta ese punto, junto con la figura que se está escaneando actualmente (¿con un carácter de puntero impreso a la izquierda del símbolo escaneado?). Si hemos interpretado correctamente el significado de Turing, este será un conjunto de símbolos enormemente largo. Pero no está claro si se debe repetir todo el código M; solo es necesaria una impresión de la instrucción del código M actual más la impresión de todas las figuras con un marcador de figura).
(vi) Turing redujo la gran cantidad posible de instrucciones en "código M" (de nuevo: el código de M que aparece en la cinta) a un pequeño conjunto canónico, uno de tres similares a este: {qi Sj Sk R ql} p. ej., si la máquina está ejecutando la instrucción #qi y el símbolo Sj está en el cuadrado que se está escaneando, entonces se imprime el símbolo Sk y se va a la derecha y luego se pasa a la instrucción ql : Las otras instrucciones son similares, codifican para "Izquierda" L y "Sin movimiento" N. Este es el conjunto que está codificado por la cadena de símbolos qi = DA...A, Sj = DC...C, Sk = DC...C, R, ql = DA...A. Cada instrucción está separada de otra por el punto y coma. Por ejemplo, {q5, S1 S0 L q3} significa: Instrucción #5: Si el símbolo escaneado es 0 , entonces se imprime en blanco , se va a la izquierda y luego se pasa a la instrucción #3. Se codifica de la siguiente manera
; DAAAAADCDLDAAA
Segunda pista: Turing está usando ideas introducidas en el artículo de Gödel, es decir, la "Gödelización" de (al menos parte de) la fórmula para Un (M). Esta pista aparece sólo como una nota al pie en la página 138 (Davis (1965), p. 138): "Una secuencia de r primos se denota por ^ (r)" ( ibíd .) [Aquí, r dentro de paréntesis está "elevado".] Esta "secuencia de primos" aparece en una fórmula llamada F^(n).
Tercera pista: Esto refuerza la segunda pista. El intento original de Turing de demostrarlo utiliza la expresión:
(Eu)N(u) y (x)(... etc. ...) [6]
Anteriormente, en el artículo, Turing había utilizado esta expresión (p. 138) y definido N(u) como "u es un entero no negativo" ( ibid .) (es decir, un número de Gödel). Pero, con las correcciones de Bernays, Turing abandonó este enfoque (es decir, el uso de N(u)) y el único lugar donde aparece explícitamente "el número de Gödel" es donde utiliza F^(n).
¿Qué significa esto para la prueba? La primera pista significa que un simple examen del código M en la cinta no revelará si el símbolo 0 es impreso alguna vez por U+"código M". Una máquina de pruebas podría buscar la aparición de DC en una de las cadenas de símbolos que representan una instrucción. Pero ¿se "ejecutará" alguna vez esta instrucción? Algo tiene que "ejecutar el código" para averiguarlo. Este algo puede ser una máquina o pueden ser líneas en una prueba formal, es decir, el Lema n.° 1.
La segunda y tercera pistas significan que, como su base es el artículo de Gödel, la prueba es difícil.
En el ejemplo que se muestra a continuación, construiremos un "teorema" simple: un pequeño programa de máquina Post-Turing que lo "ejecutará". Veremos lo mecánico que puede ser un teorema correctamente diseñado. Veremos que una demostración es justamente eso, una "prueba" del teorema que realizamos insertando un "ejemplo de demostración" al principio y viendo qué aparece al final.
Se requieren ambos lemas n.° 1 y n.° 2 para formar el "SI Y SÓLO SI" necesario (es decir, la equivalencia lógica) requerida por la prueba:
Un conjunto E es computablemente decidible si y sólo si tanto E como su complemento son computablemente enumerables. (Franzén, p. 67)
Para citar a Franzén:
Se dice que una oración A es decidible en un sistema formal S si A o su negación son demostrables en S. (Franzén, p. 65)
Franzén ha definido "demostrable" anteriormente en su libro:
Un sistema formal es un sistema de axiomas (expresados en un lenguaje definido formalmente) y reglas de razonamiento (también llamadas reglas de inferencia), que se utilizan para derivar los teoremas del sistema. Un teorema es cualquier enunciado en el lenguaje del sistema que se puede obtener mediante una serie de aplicaciones de las reglas de razonamiento, a partir de los axiomas. Una demostración es una secuencia finita de tales aplicaciones, que conduce a un teorema como su conclusión. ( ibíd. p. 17)
Así, una "oración" es una cadena de símbolos, y un teorema es una cadena de cadenas de símbolos.
Turing se enfrenta a la siguiente tarea:
convertir un "programa" de la máquina de Turing universal , y los símbolos numéricos de la cinta (las "cifras" de Turing, los símbolos "1" y "0"), en un "teorema", es decir, una cadena (monstruosamente larga) de oraciones que definen las acciones sucesivas de la máquina, (todas) las figuras de la cinta y la ubicación del "cabezal de la cinta".
Por lo tanto, la "cadena de oraciones" estará formada por cadenas de cadenas de símbolos. Los únicos símbolos individuales permitidos serán los símbolos que Gödel definió en su artículo. (En el siguiente ejemplo, utilizamos "<" y ">" alrededor de una "figura" para indicar que la "figura" es el símbolo que la máquina está escaneando).
En lo que sigue, debemos recordar que cada una de las “máquinas de computación” de Turing es un generador/creador de números binarios que comienza a trabajar en una “cinta en blanco”. Si se construye correctamente, siempre gira hasta el infinito, pero sus instrucciones son siempre finitas. En las pruebas de Turing, la cinta de Turing tenía un “extremo izquierdo” pero se extendía hacia la derecha hasta el infinito. A modo de ejemplo, a continuación supondremos que la “máquina” no es una máquina universal, sino más bien la “máquina dedicada” más simple con las instrucciones de la Tabla.
Nuestro ejemplo se basa en un modelo de máquina de Turing Post-Turing modificado . Este modelo imprime solo los símbolos 0 y 1. La cinta en blanco se considera que contiene todas las letras b. Nuestro modelo modificado requiere que agreguemos dos instrucciones más a las 7 instrucciones Post-Turing. Las abreviaturas que utilizaremos son:
R, DERECHA: mirar a la derecha y mover la cinta a la izquierda, o mover el cabezal de la cinta a la derecha.
L, IZQUIERDA: mirar a la izquierda y mover la cinta a la derecha, o mover el cabezal de la cinta a la izquierda.
E, BORRAR cuadrado escaneado (por ejemplo, dejar el cuadrado en blanco).
P0: IMPRIMIR 0 en el cuadrado escaneado.
P1: IMPRIMIR 1 en el cuadrado escaneado.
Jb_n, SALTAR-SI-en-blanco-a-instrucción_#n,
J0_n, SALTAR-SI-0-a-instrucción_#n,
J1_n, SALTAR-SI-1-a-instrucción_#n,
DETENER.
En los casos de R, L, E, P0 y P1, después de realizar su tarea, la máquina continúa con la siguiente instrucción en secuencia numérica; lo mismo ocurre con los saltos si sus pruebas fallan.
Pero, para abreviar, nuestros ejemplos solo usarán tres cuadrados. Y estos siempre comenzarán como espacios en blanco con el cuadrado escaneado a la izquierda: es decir, bbb. Con dos símbolos 1, 0 y espacio en blanco podemos tener 27 configuraciones distintas:
bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111
Debemos tener cuidado aquí, porque es muy posible que un algoritmo deje (temporalmente) espacios en blanco entre las cifras y luego vuelva y rellene algo. Lo más probable es que un algoritmo haga esto intencionalmente. De hecho, la máquina de Turing lo hace: imprime en cuadrados alternos, dejando espacios en blanco entre las cifras para poder imprimir símbolos de localización.
Turing siempre dejaba en blanco los cuadrados alternativos para que su máquina pudiera colocar un símbolo a la izquierda de una figura (o una letra si la máquina es la máquina universal y el cuadrado escaneado está realmente en el “programa”). En nuestro pequeño ejemplo, prescindiremos de esto y simplemente colocaremos símbolos ( ) alrededor del símbolo escaneado, de la siguiente manera:
b(b)0 esto significa, "La cinta está en blanco a la izquierda del espacio en blanco izquierdo pero el espacio en blanco izquierdo está 'en juego', el cuadrado escaneado está en blanco, '0', espacios en blanco a la derecha"
1(0)1 esto significa, "La cinta está en blanco a la izquierda, luego 1, el cuadrado escaneado es '0'"
Escribamos un programa sencillo:
Inicio: P1, R, P1, R, P1, H
Recuerde que siempre empezamos con una cinta en blanco. La configuración completa imprime los símbolos en la cinta seguidos de la siguiente instrucción:
configuración inicial: (b) P1,
configuración n.° 1: (1) R,
configuración n.° 2: 1(b) P1,
configuración n.° 3: 1(1) R,
configuración n.° 4: 11(b) P1,
configuración n.° 5: 11(1) H
Agreguemos “saltar” a la fórmula. Cuando lo hagamos, descubriremos por qué la configuración completa debe incluir los símbolos de cinta. (De hecho, lo veremos mejor a continuación). Este pequeño programa imprime tres “1” a la derecha, invierte la dirección y se mueve hacia la izquierda imprimiendo 0 hasta que llega a un espacio en blanco. Imprimiremos todos los símbolos que utiliza nuestra máquina:
inicio: P1, R, P1, R, P1, P0, L, J1_7, H
(b)bb P1,
(1)bb R,
1(b)b P1,
1(1)b R,
11(b) P1,
11(1) P0,
11(0) L,
1(1)0 J1_7
1(1)0 L
(1)10 J0_7
(1)10 L
(b)110 J0_7
(b)110 H
Aquí al final encontramos que un espacio en blanco a la izquierda ha “entrado en juego” por lo que lo dejamos como parte de la configuración total.
Dado que hemos hecho bien nuestro trabajo, añadimos las condiciones iniciales y vemos “hacia dónde va el teorema”. La configuración resultante (el número 110) es la DEMOSTRACIÓN.
La prueba de Turing se complica por una gran cantidad de definiciones y se confunde con lo que Martin Davis llamó "pequeños detalles técnicos" y "... detalles técnicos [que] son incorrectos tal como se dan". [c] El propio Turing publicó "Una corrección" en 1938: "El autor está en deuda con P. Bernays por señalar estos errores". [7]
En concreto, en su forma original la tercera prueba está plagada de errores técnicos. E incluso después de las sugerencias de Bernays y las correcciones de Turing, seguían existiendo errores en la descripción de la máquina universal . Y, para mayor confusión, dado que Turing no pudo corregir su artículo original, parte del texto del cuerpo del documento remite al primer intento defectuoso de Turing.
Las correcciones de Bernays se pueden encontrar en Davis (1965), pp. 152-154; el original se encuentra como "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction", Proceedings of the London Mathematical Society (2), 43 (1938), 544-546.
La versión en línea del artículo de Turing tiene estas correcciones en un apéndice; sin embargo, las correcciones a la Máquina Universal deben encontrarse en un análisis proporcionado por Emil Post .
Al principio, el único matemático que prestó atención a los detalles de la prueba fue Post (cf. Hodges p. 125), principalmente porque había llegado simultáneamente a una reducción similar del "algoritmo" a acciones primitivas similares a las de una máquina, por lo que se interesó personalmente en la prueba. Curiosamente (quizá intervino la Segunda Guerra Mundial), a Post le llevó unos diez años analizarla en el Apéndice de su artículo Recursive Unsolvability of a Problem of Thue (Insolubilidad recursiva de un problema de Thue) , 1947. [d]
Se presentan otros problemas: en su Apéndice, Post comentó indirectamente sobre la dificultad del artículo y directamente sobre su "naturaleza general" [e] y la "forma intuitiva" de las pruebas. [e] Post tuvo que inferir varios puntos:
Si nuestra crítica es correcta, se dice que una máquina no tiene círculos si es una máquina de cálculo de Turing... que imprime un número infinito de 0 y 1. Y los dos teoremas de Turing en cuestión son realmente los siguientes. No existe ninguna máquina de Turing... que, cuando se le proporcione un entero positivo arbitrario n, determine si n es el DN de una máquina de cálculo de Turing... que no tenga círculos. [En segundo lugar], no existe ninguna máquina de convenciones de Turing que, cuando se le proporcione un entero positivo arbitrario n, determine si n es el DN de una máquina de cálculo de Turing... que imprima alguna vez un símbolo dado (digamos 0). [f]
Cualquiera que haya intentado leer el periódico comprenderá la queja de Hodges:
El artículo comenzó de forma atractiva, pero pronto se hundió (al estilo típico de Turing) en una maraña de oscuros tipos góticos alemanes para desarrollar su tabla de instrucciones para la máquina universal. Los últimos en echarle un vistazo serían los matemáticos aplicados que tuvieron que recurrir a la computación práctica... (Hodges, pág. 124)
1 número computable : un número cuyo decimal es computable por una máquina (es decir, por medios finitos como un algoritmo)
2 M — una máquina con una tabla de instrucciones finita y un cabezal de escaneo/impresión. M mueve una cinta infinita dividida en cuadrados, cada uno “capaz de llevar un símbolo”. Las instrucciones de la máquina son solo las siguientes: mover un cuadrado a la izquierda, mover un cuadrado a la derecha, en el cuadrado escaneado imprimir el símbolo p, borrar el cuadrado escaneado, si el símbolo es p entonces ejecutar la instrucción aaa, si el símbolo escaneado no es p entonces ejecutar la instrucción aaa, si el símbolo escaneado no es ninguno entonces ejecutar la instrucción aaa, si el símbolo escaneado es cualquiera ejecutar la instrucción aaa [donde “aaa” es un identificador de instrucción].
3 máquina de computación — una M que imprime dos tipos de símbolos, los símbolos del primer tipo se llaman “figuras” y son solo símbolos binarios 1 y 0; los símbolos del segundo tipo son cualquier otro símbolo.
4 figuras : símbolos 1 y 0 , también conocidos como “símbolos del primer tipo”
5 m-configuration : el identificador de instrucción, ya sea un símbolo en la tabla de instrucciones o una cadena de símbolos que representan el número de instrucción en la cinta de la máquina universal (por ejemplo, "DAAAAA = #5")
6 símbolos del segundo tipo : cualquier símbolo que no sea 1 ni 0
7 circular — una máquina de cálculo fallida. No consigue imprimir, hasta el infinito, las cifras 0 o 1 que representan en binario el número que calcula
8. Sin círculos : una máquina de computación exitosa. Imprime, hasta el infinito, las cifras 0 o 1 que representan en binario el número que calcula.
9 secuencia —como en “secuencia calculada por la máquina”: símbolos del primer tipo, también conocidos como figuras o símbolos 0 y 1.
10 secuencia computable : puede ser calculada por una máquina sin círculos
11 SD – Descripción estándar: una secuencia de símbolos A, C, D, L, R, N, “;” en una cinta de máquina de Turing
12 DN — Número de descripción : una SD convertida a un número: 1=A, 2=C, 3 =D, 4=L, 5=R, 6=N, 7=;
13 M(n) — una máquina cuyo DN es el número “n”
14 satisfactorio : una SD o DN que representa una máquina sin círculos
15 U — máquina equipada con una tabla de instrucciones “universal”. Si a U se le “suministra una cinta en cuyo comienzo está escrita la SD de alguna máquina de computación M, U calculará la misma secuencia que M”.
16 β' —“beta-primed”: Un llamado “número diagonal” formado por la n-ésima cifra (es decir, 0 o 1) de la n-ésima secuencia computable [también: el número computable de H, ver más abajo]
17 u — una SD insatisfactoria, es decir, circular
18 s : satisfactorio, es decir, SD sin círculos
19 D — una máquina contenida en H (ver abajo). Cuando se le suministra la SD de cualquier máquina de computación M, D probará la SD de M y si es circular la marcará con “u” y si no tiene círculo la marcará con “s”
20 H — una máquina de computación. H calcula B', mantiene R y N. H contiene D y U y una máquina (o proceso) no especificado que mantiene N y R y proporciona a D la desviación estándar equivalente de N. E también calcula las cifras de B' y ensambla las cifras de B'.
21 R : un registro o recuento de la cantidad de SD exitosas (sin círculos) probadas por D
22 N — un número, que comienza con 1, que la máquina debe convertir en una DE. E. E mantiene N.
23 K — un número. El DN de H.
5 m-configuration — el identificador de la instrucción, ya sea un símbolo en la tabla de instrucciones o una cadena de símbolos que representan el número de la instrucción en la cinta de la máquina universal (por ejemplo, "DAAAAA = instrucción n.° 5"). En la SD de Turing, la m-configuration aparece dos veces en cada instrucción; la cadena más a la izquierda es la "instrucción actual"; la cadena más a la derecha es la siguiente instrucción.
24 configuración completa : el número (figura 1 o 0 ) del cuadrado escaneado, la secuencia completa de todos los símbolos en la cinta y la configuración m (el identificador de instrucción, ya sea un símbolo o una cadena de símbolos que representan un número, por ejemplo, "instrucción DAAAA = #5")
25 RSi(x, y) — "en la configuración completa x de M el símbolo en el cuadrado y es Si; "configuración completa" es la definición n.° 5
26 I(x, y) — "en la configuración completa x de M se escanea el cuadrado y"
27 Kqm(x) — "en la configuración completa x de M la configuración de la máquina (número de instrucción) es qm"
28 F(x,y) — "y es el sucesor inmediato de x" (sigue el uso de "f" de Gödel como función sucesora).
29 G(x,y) — "x precede a y", no necesariamente inmediatamente
30 Inst{qi, Sj Sk L ql} es una abreviatura, al igual que Inst{qi, Sj Sk R ql} e Inst{qi, Sj Sk N ql} . Véase más abajo.
Turing reduce su conjunto de instrucciones a tres “formas canónicas”: una para izquierda, otra para derecha y otra para no moverse. Si y Sk son símbolos en la cinta.
Por ejemplo, las operaciones en la primera línea son PSk = IMPRIMIR el símbolo Sk de la colección A, C, D, 0, 1, u, v, w, x, y, z, : , luego mover la cinta a la IZQUIERDA.
Estos los abrevió además como: (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm
En la Prueba #3, llama al primero de estos “Inst{qi Sj Sk L ql}”, y muestra cómo escribir la SD de la máquina entera como la conjunción lógica (OR lógico): esta cadena se llama “Des(M)”, como en “Descripción-de-M”, es decir, si la máquina imprime 0 y luego 1 y 0 en cuadrados alternos hacia la derecha hasta el infinito, podría tener la tabla (un ejemplo similar aparece en la página 119):
q1, en blanco, P0, R, q2
q2, en blanco, P-en blanco, R, q3
q3, en blanco, P1, R, q4
q4, en blanco, P-en blanco, R, q1
(Esto se ha reducido a la forma canónica con las instrucciones “p-blank”, por lo que difiere un poco del ejemplo de Turing). Si las ponemos en la “forma Inst()”, las instrucciones serán las siguientes (recordando: S0 está en blanco, S1 = 0, S2 = 1):
Inst. {q1 S0 S1 R q2}
Inst. {q2 S0 S0 R q3}
Inst. {q3 S0 S2 R q4}
Inst. {q4 S0 S0 R q1}
La reducción a la Descripción Estándar (DE) será:
; DADDCRDAA; DAADDRDAAA ; DAAADDCCRDAAAA ; DAAAADDRDA ;
Esto coincide con el ejemplo que aparece en el libro (habrá un espacio en blanco entre cada letra y número). La máquina universal U utiliza los cuadrados en blanco alternos como lugares para colocar "punteros".