Prueba de Turing

turing ' s Prueba es una prueba de Alan Turing, publicada por primera vez en noviembre de 1936 con el título " en números computables, con una aplicación al Título entcheidungsproblem " ;. Fue la segunda prueba (después del teorema de la iglesia) de la negación de Hilbert ' s entscheidungsproblem ; es decir, la conjetura de que un sí, no se pueden responder a las preguntas puramente matemáticas, no se pueden responder a las preguntas; Más técnicamente, que algunos problemas de decisión son " indecidibles " En el sentido de que no hay un algoritmo único que infaliblemente le da un correcto " sí " o " no " Responda 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 mostraré que no hay un método general que diga si una fórmula dada u es demostrable en << b> k [ Principia Mathematica ] " ;.

Turing siguió esta prueba con otras dos. El segundo y el tercero confían en el primero. Todos confían en su desarrollo de máquinas de computación y#34 de tipo máquina de escribir " que obedece un conjunto simple de reglas y su posterior desarrollo de A " Universal Computing Machine ".

Resumen de las pruebas

En su prueba de que el problema de enscheidungs no puede tener ninguna solución, Turing procedió de dos pruebas que llevarían a su prueba final. Su primer teorema es más relevante para el problema de detención, el segundo es más relevante para el teorema de Rice.

Primera prueba : que no " Máquina de computación " existe que puede decidir si una máquina arbitraria " Machine " (como se representa por un número entero 1, 2, 3, ...) es " Free Free " (es decir, continúa imprimiendo su número en binary 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 usar el proceso diagonal " de hecho, muestra que su máquina (llamada H) no puede calcular su propio número, y mucho menos todo el número diagonal (Cantor ' S Argumento diagonal): " La falacia en el argumento radica en la suposición de que B [el número diagonal] es computable " 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 mostrar más que no puede haber una máquina que, cuando, cuando, cuando sea, cuando, cuando, cuando, cuando, cuando, cuando sea, cuando, cuando no pueda haber suministrado con el S.D [" programa "] de una máquina arbitraria M, determinará si M imprime un símbolo dado (0 por ejemplo) "

tercera prueba : " correspondiente a cada máquina de computación M construimos una fórmula un (m) y mostramos que, si existe un método general para determinar si un (m) es Probable, entonces hay un método general para determinar si M alguna vez imprime 0 ".

La tercera prueba requiere el uso de la lógica formal para probar un primer lema, seguido de una breve a prueba de palabras del segundo:

Lemma 1: Si S1 [symbol "0"] aparece en la cinta en una configuración completa de M, entonces Un(M) es provable.
Lemma 2: [The converse] Si Un(M) es provable entonces S1 [symbol "0"] aparece en la cinta en una configuración completa de M.

Finalmente, en sólo 64 palabras y símbolos, Turing demuestra por reductio ad absurdum que "el problema de Hilbert Entscheidungs no puede tener solución".

Resumen de la primera prueba

Turing creó una maraña de abreviaturas. Consulte el glosario al final del artículo para obtener definiciones.

Algunas aclaraciones clave:

Máquina de Turing H está tratando de imprimir un número diagonal de 0s y 1s.
Este número diagonal se crea cuando H realmente "simula" cada máquina "sucesiva" bajo evaluación e imprime la "figura" R-th (1 o 0) de la máquina "sucesiva" R-th.

Turing dedicó gran parte de su artículo a "construir" sus máquinas para convencernos de su verdad. Esto fue requerido por su uso de la forma de prueba reductio ad absurdum. Debemos enfatizar el carácter "constructivo" naturaleza de esta prueba. Turing describe lo que podría ser una máquina real, realmente edificable. El único elemento cuestionable es la existencia de la máquina D, que esta prueba finalmente demostrará que es imposible.

Turing comienza la prueba con la afirmación de la existencia de una máquina D de “decisión/determinación”. Cuando se le suministra cualquier S.D (cadena de símbolos A, C, D, L, R, N, punto y coma “;”), determine si este S.D (cadena de símbolo) representa una "máquina informática" eso es "circular" — y por tanto "u"insatisfactorio" — o "sin círculos" — y por lo tanto "satisfactorio s".

Turing ha demostrado anteriormente en su comentario que todas las máquinas de computación — máquinas que computan un número como 1s y 0s para siempre— pueden ser escritas como S.D en la cinta de la “máquina universal” U. La mayor parte de su trabajo previo a su primera prueba se gasta demostrando que una máquina universal existe realmente, es decir.
Existe realmente una máquina universal U
Para cada número N, existe realmente un S.D único,
Cada máquina de Turing tiene un S.D
Cada S.D en la cinta de U puede ser “corrido” por U y producirá la misma “salida” (figuras 1, 0) como la máquina original.

Turing no hace comentarios sobre cómo realiza su trabajo la máquina D. A efectos de argumentación, suponemos que D primero comprobaría si la cadena de símbolos está "bien formada"; (es decir, en forma de algoritmo y no solo una mezcla de símbolos), y si no, deséchelo. Entonces iría a “cazar en círculos”. Para ello quizás se utilizarían “heurísticas” (trucos: enseñados o aprendidos). A los efectos de la prueba, estos detalles no son importantes.

Turing luego describe (de forma bastante vaga) el algoritmo (método) que debe seguir una máquina a la que 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 está expresado en la tabla de instrucciones de H, o quizás en la Descripción Estándar de H en cinta y unida a la máquina universal U; Turing no especifica esto.

En el curso de describir la máquina universal U, Turing ha demostrado que el S.D de una máquina (cadena de letras similares a un “programa”) se puede convertir en un entero (base 8) y viceversa. Cualquier número N (en la base 8) se puede convertir a un S.D con los siguientes reemplazos: 1 por A, 2 por C, 3 por D, 4 por L, 5 por R, 6 por N, 7 por semicolon ";".

Como resulta, el número único de máquina H (D.N) es el número "K". Podemos inferir que K es un número enormemente largo, tal vez decenas de miles de dígitos largos. Pero esto no es importante para lo que sigue.

Máquina H es responsable de la conversión cualquiera número N en una cadena de símbolo S.D equivalente para la prueba de sub-máquina D. (En la parlanza de programación: H pasa una "S.D" arbitraria a D, y D devuelve "satisfactoria" o "insatisfactoria".) Máquina H también es responsable de mantener un tally R (“Record”?) de números exitosos (suponemos que el número de “sucesos” S.D, es decir R, es mucho menos que el número de S.D probado, es decir, N). Por último, H imprime en una sección de su cinta un número diagonal “beta-primed” B’. H crea esta B’ por “simular” (en el sentido de la computadora) las “mociones” de cada máquina/número “satisfactoria”; eventualmente esta máquina/número bajo prueba llegará a su “figura” Rth (1 o 0), y H la imprimirá. H entonces es responsable de “limpiar el desorden” dejado por la simulación, aumentar N y seguir adelante con sus pruebas, ad infinitum.

Nota: Todas estas máquinas que H está buscando son lo que Turing llamó "máquinas informáticas". Estos calculan números decimales binarios en un flujo interminable de lo que Turing llamó "cifras": sólo los símbolos 1 y 0.

Un ejemplo para ilustrar la primera prueba

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 S.D's (cadenas de símbolos) y se los ha pasado a D para su prueba. Como consecuencia, H ha sumado 5 números satisfactorios y ha corrido 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. a su quinta cifra. El recuento ahora es N = 13472, R = 5 y B' = ".10011" (Por ejemplo). H limpia el desorden de su cinta y continúa:

H incrementa N = 13473 y convierte "13473" a la cadena de símbolos ADRLD. Si la submáquina D considera que ADLRD es insatisfactorio, entonces H deja el registro de conteo R en 5. H incrementará el número N a 13474 y continuará adelante. Por otro lado, si D considera que ADRLD es satisfactorio, entonces H incrementará R a 6. H convertirá N (nuevamente) en ADLRD [esto es sólo un ejemplo, ADLRD probablemente sea inútil] y lo “ejecutará” usando la máquina universal U hasta esta máquina bajo prueba (U "en ejecución" ADRLD) imprime 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 finalmente llega a su propio número menos 1, es decir, N = K-1 = 4335...3214, y este número no tiene éxito. Luego H incrementa N para producir K = 4355...3215, es decir, su propio número. H convierte esto a “LDDR...DCAR” y lo pasa a la máquina de decisiones D. La máquina de decisiones D debe devolver “satisfactorio” (es decir: H debe por definición seguir y seguir 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 K bajo prueba en su SD y usa U para simularlo. Pero esto significa que H simulará sus propios movimientos. ¿Qué es lo primero que hará la simulación? Esta simulación K-aka-H crea un nuevo N o "restablece" el "antiguo" N a 1. Este "K-aka-H" crea una nueva R o "restablece" la "antigua" R a 0. Old-H "ejecuta" la nueva "K-aka-H" hasta llegar a su cifra número 12.

Pero nunca llega a la cifra 13; K-aka-H finalmente llega a 4355...3215, nuevamente, y K-aka-H debe repetir la prueba. K-aka-H nunca alcanzará la cifra 13. La máquina H probablemente simplemente imprime copias de sí misma ad infinitum en una cinta en blanco. Pero esto contradice la premisa de que H es una máquina informática satisfactoria y no circular que sigue imprimiendo los números diagonales 1 y 0 indefinidamente. (Veremos lo mismo si N se restablece a 1 y R se restablece a 0).

Si el lector no cree esto, puede escribir un "stub" para la máquina de decisiones D (el trozo "D" devolverá "satisfactorio") y luego ver por sí mismos qué sucede en el instante en que la máquina H encuentra su propio número.

Resumen de la segunda prueba

Con menos de una página, el paso de las premisas a la conclusión es oscuro.

Turing procede mediante una reductio ad absurdum. Afirma la existencia de una máquina E, que cuando se le da la S.D (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 informática".

Dada la existencia de la máquina E, Turing procede de la siguiente manera:

1. Si la máquina E existe entonces una máquina G existe que determina si M imprime 0 infinitamente a menudo, Y
2. Si E existe entonces otro proceso existe [podemos llamar al proceso/machine G' para referencia] que determina si M imprime 1 infinitamente a menudo, THEREFORE
3. Cuando combinamos G con G' tenemos un proceso que determina si M imprime un infinito de figuras, Y
4. Si el proceso "G con G" determina M imprime un infinito de figuras, entonces "G con G" ha determinado que M es libre de círculos, PERO
5. Este proceso "G con G" que determina si M está libre de círculos, por prueba 1, no puede existir, THEREFORE
6. Máquina E no existe.

Detalles de la segunda prueba

La dificultad en la demostración es el paso 1. Ayudará al lector darse cuenta 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 recorrer todo el lote buscando: “Coches con neumáticos pinchados (malos)”. Después de aproximadamente una hora hemos encontrado dos “coches con neumáticos defectuosos”. Ahora podemos decir con certeza que “algunos coches tienen neumáticos malos”. O podríamos decir: "No es cierto eso de 'Todos los coches tienen buenos neumáticos'". O: “Es cierto que: 'no todos los coches tienen buenos neumáticos'. Vayamos a otro lote. Aquí descubrimos que “Todos los coches tienen buenos neumáticos”. Podríamos decir: "No hay un solo caso en el que un automóvil tenga una llanta defectuosa". Así vemos que, si podemos decir algo sobre cada automóvil 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 {M1, M2, M3, M 4,..., Mn} y sobre cada uno escribe una frase: “X imprime al menos un 0” y permite sólo dos “valores de verdad” , Verdadero = en blanco o Falso =:0:. Uno por uno, determina el valor de verdad de la oración para cada máquina y crea una serie de espacios en blanco o:0:, o alguna combinación de estos. Podríamos obtener algo como esto: “M1 imprime un 0” = Verdadero Y “M2 imprime un 0” = Verdadero Y “M 3 imprime un 0” = Verdadero Y “M4 imprime un 0” = Falso,... Y “Mn imprime un 0” = Falso. El consigue la cuerda

BBB:0::0::0:...:0:... ad infinitum

si hay un número infinito de máquinas Mn. Si, por otro lado, cada máquina hubiera producido un resultado "Verdadero" entonces la expresión en la cinta sería

BBBBB... BBBB... ad infinitum

Así, Turing ha convertido declaraciones sobre cada máquina considerada por separado en una única "declaración" (cadena) sobre todos ellos. Dada la máquina (la 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 efectivamente lo hace, por lo que sabemos que no todas las Los M en nuestra secuencia imprimen 0. Pero el segundo ejemplo muestra que, dado que la cadena está en blanco, cada Mn en 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:

M = título...AB01AB0010AB...

Turing crea otra máquina F que toma M y genera una secuencia de Mn que convierten sucesivamente los primeros n 0 en “barra 0” (0):

Afirma, sin mostrar detalles, que esta máquina F es verdaderamente edificable. Podemos ver que podrían suceder una de un par de cosas. F puede quedarse sin máquinas que tengan ceros, o puede que tenga que seguir ad infinitum creando máquinas 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 que comienza 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 que 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á 0’s, nunca, si toda la impresión de Mn 0’s, OR,
G imprimirá ad infinitum 0’s si toda la impresión de M no 0’s, OR,
G imprimirá 0's por un tiempo y luego para.

Ahora, ¿qué sucede cuando aplicamos E a G?

Si E(G) determina que G nunca imprime un 0 entonces sabemos que todos los Mn han impreso 0’s. Y esto significa que, porque todo el Mn vino de M, que M en sí imprime 0’s ad infinitum, O
Si E(G) determina que G hace imprimir un 0 entonces sabemos que no todas las huellas de Mn 0’s; por lo tanto, M no imprime 0’s ad infinitum.

Como podemos aplicar el mismo proceso para determinar si M imprime 1 infinitamente veces. Cuando combinamos estos procesos, podemos determinar que M continúa imprimiendo o no 1 y 0 ad infinitum. Por tanto, tenemos un método para determinar si M no tiene círculos. Según la Prueba 1, esto es imposible. Entonces, la primera afirmación de que E existe es incorrecta: E no existe.

Resumen de la tercera prueba

Aquí Turing demuestra "que el problema de Hilbert Entscheidungs no puede tener solución". aquí el

...show(s) que no puede haber un proceso general para determinar si una fórmula dada U del cálculo funcional K es provable. ()i)

Tanto el lema n.° 1 como el n.° 2 son necesarios para formar el "SI Y SÓLO SI" (es decir, equivalencia lógica) requerida por la prueba:

Un conjunto E es computadamente decidable si y sólo si ambos E y su complemento son computadamente enumerables (Franzén, pág. 67)

Turing demuestra la existencia de una fórmula Un(M) que dice, en efecto, que "en alguna configuración completa de M, 0 aparece en el cinta" (pág. 146). Esta fórmula es VERDADERA, es decir, es "construible", y él muestra cómo hacerlo.

Luego, Turing demuestra dos lemas; el primero requiere todo el trabajo duro. (El segundo es lo contrario del primero.) Luego usa reductio ad absurdum para probar su resultado final:

1. Existe una fórmula Un(M). Esta fórmula es VERDAD, Y
2. Si Entscheidungsproblem puede ser resuelto A continuación un proceso mecánico existe para determinar si Un(M) is provable (derivable), AND
3. Por Lemmas 1 y 2: Un(M) is provable IF AND ONLY IF 0 aparece en alguna "configuración completa" de M, AND
4. IF 0 aparece en alguna "configuración completa" de M THEN existe un proceso mecánico que determinará si M arbitrarios alguna vez impresos 0, Y
5. Por Proof 2 no existe ningún proceso mecánico que determinará si M arbitrarios alguna vez imprimen 0, allí
6. Un(M) is not provable (Es TRUE, pero no provable) que significa que Entscheidungsproblem es insolvable.

Detalles de la tercera prueba

[Si los lectores tienen la 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 contar con una sólida formación en (i) lógica (ii) el artículo de Kurt Gödel: "Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados". Para obtener ayuda con el artículo de Gödel, pueden consultar, p. Ernest Nagel y James R. Newman, La prueba de Gödel, New York University Press, 1958.]

Para seguir los detalles técnicos, el lector deberá comprender la definición de término "demostrable" y esté atento a las "pistas" importantes.

"Demostrable" significa, en el sentido de Gödel, que (i) el sistema de axiomas en sí es lo suficientemente poderoso como para producir (expresar) la oración "Esta oración es demostrable", y (ii) que en cualquier " bien formado" probar los símbolos mediante axiomas, definiciones y sustitución de 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" de la máquina M en la cinta de una "máquina universal" U. Esto requiere que el lector conozca algunas particularidades de la máquina universal U de Turing y el esquema de codificación.

(i) La máquina universal es un conjunto de máquinas "universales" instrucciones que residen en una "tabla de instrucciones". Aparte de esto, en la cinta de U, una "máquina informática" M residirá 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 sólo indirectamente ordenando a U que los imprima.

(ii) El "código de máquina" de M consta sólo de unas pocas letras y el punto y coma, es decir, D, C, A, R, L, N,;. En ninguna parte del "código" de M las "cifras" (Símbolos) 1 y 0 aparecen alguna vez. Si M quiere que U imprima un símbolo de la colección blank, 0, 1 entonces usa uno de los siguientes códigos para decirle a U que los imprima. Para hacer las cosas más confusas, Turing llama a estos símbolos S0, S1 y S2, es decir.

blanco S0 = D

0 S1 = DC

1 S2 = DCC

(iii) Una "máquina informática", ya sea integrada directamente en una mesa (como muestran sus primeros ejemplos), o como código de máquina M en una cinta U de máquina universal, imprime su número en una cinta en blanco (a la derecha del código M, si lo hay) como 1s y 0s siempre avanzando hacia la derecha.

(iv) Si una "máquina informática" es U+"código M", luego "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 terminar, debido a la suposición de que estos códigos M son algoritmos finitos), las "cifras" comenzará como 1s y 0s en cuadrados alternos, avanzando hacia la derecha para siempre. Turing utiliza los cuadrados alternativos (en blanco) (llamados "E"- "borrables"- cuadrados) para ayudar a codificar U+"M" realice un seguimiento de dónde están los cálculos, tanto en el código M como en las "cifras" que la máquina está imprimiendo.

(v) Una "configuración completa" es una impresión de todos los símbolos en la cinta, incluido el código M y las "cifras" 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 todo el código M debe repetirse; sólo es necesaria la impresión de la instrucción del código M actual más la impresión de todas las figuras con un marcador de figuras).

(vi) Turing redujo el gran número posible de instrucciones en el "código M" (nuevamente: el código de M que aparecerá en la cinta) a un pequeño conjunto canónico, uno de tres similares a este: {qi Sj Sk R ql} p.e. Si la máquina está ejecutando la instrucción #qi y el símbolo Sj está en el cuadrado que se está escaneando, imprima el símbolo Sk y vaya a la derecha y luego vaya a la instrucción ql: Las otras instrucciones son similares, codificando para " Izquierda" L y "Sin movimiento" N. Es este conjunto el 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 punto y coma. Por ejemplo, {q5, S1 S0 L q3} significa: Instrucción n.° 5: si el símbolo escaneado es 0, imprima en blanco, vaya a la izquierda y luego vaya a la instrucción n.° 3. Está codificado de la siguiente manera

; D A A A A A D C D L D A A A

Segunda pista: Turing está utilizando 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 nota a pie de página en la página 138 (Davis (1965), p. 138): "Una secuencia de r números primos se denota por ^(r)" (ibid.) [Aquí, r dentro de paréntesis está "elevada".] Esta "secuencia de números 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) " x)(... etc.)

Anteriormente en el artículo, Turing había usado esta expresión (p. 138) y había definido N(u) en el sentido de que "u es un número 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 "el número de Gödel" aparece explícitamente es donde usa 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 alguna vez se imprime un símbolo 0 mediante 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 alguna vez se “ejecutará” esta instrucción? Algo tiene que "ejecutar el código" descubrir. 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 fundamento es el artículo de Gödel, la prueba es difícil.

En el siguiente ejemplo, construiremos un "teorema" simple: un pequeño programa de máquina de Post-Turing "ejecútelo". Veremos cuán mecánico puede ser un teorema diseñado adecuadamente. Una prueba, como veremos, es justamente eso, una "prueba" del teorema que hacemos insertando un "ejemplo de prueba" al principio y ver qué aparece al final.

Tanto el lema n.° 1 como el n.° 2 son necesarios para formar el "SI Y SÓLO SI" (es decir, equivalencia lógica) requerida por la prueba:

Un conjunto E es computadamente decidable si y sólo si ambos E y su complemento son computadamente enumerables. (Franzén, pág. 67)

Citando a Franzén:

A sentence A is said to be decidable in a formal system S if either A or its negation is provable in S. (Franzén, p. 65)

Franzén ha definido "demostrable" anteriormente en su libro:

Un sistema formal es un sistema axiomas (expresado en algún lenguaje formalmente definido) y reglas de razonamiento (también llamadas reglas de inferencia), utilizado para derivar teoremas del sistema. A theorem es cualquier declaración en el lenguaje del sistema obtenido por una serie de aplicaciones de las reglas del razonamiento, empezando por los axiomas. A prueba es una secuencia finita de tales aplicaciones, que conduce a un teorema como su conclusión. ()ibíd. p. 17)

Por tanto, una "frase" 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 una máquina de Turing Universal "programa", y los símbolos numéricos en la cinta (Turing's "figuras", símbolos "1" y "0"), en un "teorema" — es decir, un (muy largo) cadena de oraciones que define las acciones sucesivas de la máquina, (todas) las figuras de la cinta, y la ubicación de la "cabeza de cinta".

Así, la "cadena de oraciones" serán cadenas de cadenas de símbolos. Los únicos símbolos individuales permitidos provendrán de los símbolos definidos por Gödel en su artículo. (En el siguiente ejemplo usamos "<" y ">" alrededor de un "cifra" para indicar que la "cifra" es el símbolo que está escaneando la máquina).

Un ejemplo para ilustrar la tercera prueba

A continuación, debemos recordar que cada una de las “máquinas informáticas” de Turing es un generador/creador de números binarios que comienza a trabajar en una “cinta en blanco”. Bien construido, siempre funciona hasta el infinito, pero sus instrucciones son siempre finitas. En las pruebas de Turing, la cinta de Turing tenía un “extremo izquierdo” pero el derecho se extendía hasta el infinito. A modo de ejemplo a continuación, asumiremos que la "máquina" no es una máquina universal, sino más bien una "máquina dedicada" más simple con las instrucciones de la Tabla.

Nuestro ejemplo se basa en un modelo de máquina Post-Turing modificado de una máquina de Turing. Este modelo imprime solo los símbolos 0 y 1. La cinta en blanco se considera toda b's. Nuestro modelo modificado requiere que agreguemos dos instrucciones más a las 7 instrucciones Post-Turing. Las abreviaturas que utilizaremos son:

R, DERECHO: mire a la derecha y mueva la cinta a la izquierda, o mueva la cabeza de cinta derecha
L, LEFT: mira a la izquierda y mueve la cinta derecha, o mueve la cabeza de cinta izquierda
E, ERASE escaneado cuadrado (por ejemplo, hacer blanco cuadrado)
P0: PRINT 0 en cuadrado escaneado
P1,: PRINT 1 en cuadrado escaneado
Jb_n, JUMP-IF-blank-to-instruction,
J0_n, JUMP-IF-0-to-instruction_#n,
J1_n, JUMP-IF-1-to-instrucntion_#n,
HALT.

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, por brevedad, nuestros ejemplos solo usarán tres cuadrados. Y estos siempre comenzarán con espacios en blanco con el cuadrado escaneado a la izquierda: es decir, bbb. Con dos símbolos 1, 0 y en blanco podemos tener 27 configuraciones distintas:

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 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 figuras y luego regrese y complete algo. Lo más probable es que un algoritmo haga esto intencionalmente. De hecho, la máquina de Turing hace esto: imprime en cuadrados alternos, dejando espacios en blanco entre las figuras para poder imprimir símbolos localizadores.

Turing siempre dejaba cuadrados alternos en blanco 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 renunciaremos a esto y simplemente colocaremos símbolos () alrededor del símbolo escaneado, de la siguiente manera:

b(b)0 esto significa, "Tape es blanco-a-izquierda de blanco izquierdo pero queda en blanco es 'en juego', el escaneo-cuare-es-blank, '0', blancos-a-derecha"
1(0)1 esto significa, "Tape es blanco a la izquierda, entonces 1, cuadrado escaneado es '0'"

Escribamos un programa simple:

inicio: P1, R, P1, R, P1, H

Recuerde que siempre comenzamos con cinta en blanco. La configuración completa imprime los símbolos en la cinta seguidos de la siguiente instrucción:

start config: (b) P1,
config #1: (1) R,
c) 1 b) P1,
config #3: 1(1) R,
config #4: 11(b) P1,
config #5: 11(1) H

Agreguemos “saltar” a la fórmula. Cuando hacemos esto descubrimos por qué la configuración completa debe incluir los símbolos de la cinta. (En realidad, lo vemos 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 ceros hasta que encuentra un espacio en blanco. Imprimiremos todos los símbolos que utiliza nuestra máquina:

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 nos encontramos con 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 nuestro trabajo correctamente, sumamos las condiciones iniciales y vemos “hacia dónde va el teorema”. La configuración resultante, el número 110, es la PRUEBA.

• La primera tarea de Turing tuvo que escribir una expresión generalizada usando símbolos lógicos para expresar exactamente lo que su Un(M) haría.
• La segunda tarea de Turing es "Gödelizar" este enormemente largo cordón de simbolos usando la técnica de Gödel de asignar primos a los símbolos y elevar los primos a los primeros poderes, por el método de Gödel.

Complicaciones

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 proporcionan". El propio Turing publicó "Una corrección" en 1938: "El autor está en deuda con P. Bernays por señalar estos errores".

Específicamente, en su forma original, la tercera prueba está muy estropeada por errores técnicos. E incluso después de la victoria de Bernays. sugerencias y correcciones de Turing, quedaron errores en la descripción de la máquina universal. Y de manera confusa, dado que Turing no pudo corregir su artículo original, parte del texto dentro del cuerpo recuerda al defectuoso primer esfuerzo de Turing.

Bernays' se pueden encontrar correcciones en Davis (1965), págs. 152-154; el original se encuentra como "Sobre números computables, con una aplicación al Entscheidungsproblem". Una corrección," Actas de la Sociedad Matemática de Londres (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 Universal Machine deben encontrarse en un análisis proporcionado por Emil Post.

Al principio, el único matemático que prestó mucha atención a los detalles de la demostración 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 máquinas, por lo que se interesó personalmente en la prueba. Curiosamente (tal vez intervino la Segunda Guerra Mundial) le tomó a Post unos diez años analizarlo en el Apéndice de su artículo Recursive Unsolvability of a Problem of Thue, 1947.

Se presentan otros problemas: en su Apéndice la publicación comentó indirectamente la dificultad del artículo y directamente su "naturaleza esquemática" y "forma intuitiva" de las pruebas. Post tuvo que inferir varios puntos:

Si nuestra crítica es correcta, se dice que una máquina está libre de círculos si es una máquina de computación Turing... que imprime un número infinito de 0s y 1s. Y los dos teoremas de Turing en cuestión son realmente los siguientes. No hay Turing... máquina que, cuando se suministra con un número de entero positivo arbitrario, determinará si n es el D.N de una máquina de computación Turing... libre de círculos. [Segunda], No hay ninguna convención de Turing-máquina que, cuando se suministra con un entero positivo arbitrario n, determinará si n es el D.N de una máquina de computación Turing... que alguna vez imprime un símbolo dado (0 decir).

Cualquiera que haya intentado leer el artículo entenderá las palabras de Hodges. queja:

El periódico comenzó de manera atractiva, pero pronto se hundió (de manera típica de Turing) en un espeso de tipo gótico alemán oscuro para desarrollar su tabla de instrucciones para la máquina universal. La última gente para echarle un vistazo sería los matemáticos aplicados que tenían que recurrir a la computación práctica... (Hodges p. 124)

Glosario de términos utilizados por Turing

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 de ellos “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 realizar la instrucción aaa, si el símbolo escaneado no es p entonces realice la instrucción aaa, si el símbolo escaneado es ninguno, entonces realice la instrucción aaa, si el símbolo escaneado es cualquiera, realice 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 “cifras” y son solo símbolos binarios 1 y 0; Los símbolos del segundo tipo son cualquier otro símbolo.

4 cifras: símbolos 1 y 0, también conocidos como “símbolos del primer tipo”

5 configuración m — 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 distinto de 1 y 0

7 circular: una máquina informática fallida. No logra 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 informática 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, también conocidos como símbolos 0 y 1.

10 secuencia computable: puede calcularse mediante una máquina sin círculos

11 S.D – Descripción estándar: una secuencia de símbolos A, C, D, L, R, N, “;” en una cinta de la máquina de Turing

12 D.N — Número de descripción: un S.D convertido en un número: 1=A, 2=C, 3 =D, 4=L, 5=R, 6=N, 7=;

13 M(n) — una máquina cuyo D.N es el número “n”

14 satisfactorio: un S.D o D.N que representa una máquina sin círculos

15 U: una máquina equipada con una tabla de instrucciones “universal”. Si U "recibe una cinta en cuyo comienzo está escrita la SD de alguna máquina informática M, U calculará la misma secuencia que M".

16 β'—“beta-preparado”: el llamado “número diagonal” formado por la enésima cifra (es decir, 0 o 1) de la enésima secuencia computable [ también: el número computable de H, ver más abajo]

17 u — un SD insatisfactorio, es decir, circular

18 s — satisfactorio, es decir, S.D sin círculos

19 D: una máquina contenida en H (ver más abajo). Cuando se suministra con el SD de cualquier máquina informática M, D probará el SD de M y, si es circular, márquelo con "u" y si no tiene círculo, márquelo con "s".

20 H: una máquina informática. H calcula B', mantiene R y N. H contiene D y U y una máquina (o proceso) no especificada que mantiene N y R y proporciona a D la SD 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 S.D exitosas (sin círculos) probadas por D

22 N: un número, que comienza con 1, que la máquina E convertirá en un S.D. E mantiene N.

23 K: un número. El D.N de H.

Necesario para Prueba #3

5 configuración m: 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 (p. ej. "DAAAAA = instrucción #5"). En el SD de Turing, la configuración m 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 (cifra 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 #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 Gödel de "f" 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} y Inst{qi , Sj Sk S N ql}. Vea abajo.

Turing reduce su conjunto de instrucciones a tres “formas canónicas”: una para izquierda, derecha y sin movimiento. Si y Sk son símbolos en la cinta.

Por ejemplo, las operaciones en la primera línea son PSk = PRINT símbolo Sk de la colección A, C, D, 0, 1, u, v, w, x, y, z,:, luego mueva 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 toda la máquina S.D 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, luego 1 y 0 en cuadrados alternos hacia la derecha hasta el infinito, podría tener la tabla (aparece un ejemplo similar en la página 119):

q1, blanco, P0, R, q2
q2, en blanco, P-blank, R, q3
q3, blanco, P1, R, q4
q4, blanco, P-blank, 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 los pones en el “formulario 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 (D.S) será:

; D A D D D D R D A A; D A A D D R D A A A A; D A A A D D C R D A A A A A A A; D A A A A D D R D A;

Esto concuerda con su ejemplo en el libro (habrá un espacio en blanco entre cada letra y número). La máquina universal U utiliza los cuadrados en blanco alternativos como lugares para colocar "punteros".