¿La prueba de indecidibilidad del problema de detención engaña al revertir los resultados?

Tengo problemas para entender el problema de Turing.

Su prueba asume que existe una máquina mágica que podría determinar si una computadora se detendría o realizaría un bucle para siempre para una entrada determinada. Luego conectamos otra máquina que invierte la salida y tenemos una contradicción y, por lo tanto, no puede existir.$H$$H$

Mi preocupación es que parece que estamos diciendo que una respuesta es incorrecta porque la revertimos. Como analogía, si hay una máquina llamada que genera una respuesta correcta en ciertas entradas y una respuesta incorrecta en otras. Luego adjuntamos otra máquina que invierte el resultado de para que la combinación de las dos máquinas tenga una contradicción con la forma en que se defineLas dos máquinas ahora generan respuestas incorrectas para las entradas que está definida para generar respuestas correctas y genera respuestas correctas para las entradas que está definida para generar respuestas incorrectas. ¿Se llamaría esto una contradicción y, por lo tanto, no existe una máquina que genere respuestas correctas en algunas entradas y respuestas incorrectas en otras?$A$A A $A$$A$$A$$A$

Versión corta: las salidas de las máquinas no son correctas o incorrectas, son simplemente contradictorias, lo que demuestra que la máquina inicial que decide si la máquina de entrada se detiene en la cadena dada o no puede existir.

Versión larga : Primero esbozaremos la prueba (o al menos una versión de la misma, hay muchas).

1. Supongamos que tenemos una máquina de Turing que decide si la máquina de Turing detiene en la entrada o no.M $\mathrm{HALT}(\langle M\rangle, x)$$M$$x$
2. Usando construimos una máquina que usa para verificar si detiene en o no, luego hace lo contrario, es decir, si detiene en , bucles, si no se detiene en , detiene.F L I P ( ⟨ M ⟩ , x ) H A L T M x M x F L I P M x F L I $\mathrm{HALT}$$\mathrm{FLIP}(\langle M\rangle, x)$$HALT$$M$$x$$M$$x$$\mathrm{FLIP}$$M$$x$$\mathrm{FLIP}$
3. Finalmente creamos una TM (se me acabaron los buenos nombres), que toma la descripción de una TM y ejecuta con entrada , generando cualquier salida .F L I P ( ⟨ M ⟩ , ⟨ M ⟩ ) F L I $\mathrm{C}(\langle M \rangle)$$\mathrm{FLIP}$$(\langle M \rangle, \langle M \rangle)$$\mathrm{FLIP}$

Es importante tener en cuenta que mientras exista el decisor , cada uno de estos pasos es simple de implementar; solo tiene que usar para verificar qué hacer, y simplemente duplica su entrada para pasar a .F L I P H A L T C F L I $\mathrm{HALT}$$\mathrm{FLIP}$$\mathrm{HALT}$$\mathrm{C}$$\mathrm{FLIP}$

La contradicción surge cuando miramos lo que sucede cuando ejecutamos . O bien se detiene cuando se administra a sí misma como la entrada o no. decidirá esto:C H A L $\mathrm{C}(\langle\mathrm{C}\rangle)$$\mathrm{C}$$\mathrm{HALT}$

• Si detiene en la entrada , dirá , pero luego repetirá, entonces repetirá , contradiciendo . ⟨ C ⟩ H A L T Y e s F L I P C H A L $\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{Yes}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$
• Si bucle en la entrada , dirá , pero luego se detendrá, entonces también detener, contradiciendo . ⟨ C ⟩ H A L T N O F L I P C H A L $\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{No}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$

Como cada uno de los pasos en la construcción es claramente correcto, solo podemos concluir que no puede existir; hemos construido un caso en el que no importa lo que diga, no puede decidir qué generar, es decir, el problema es indecidible. Solo para insistir un poco, no puede existir, es decir, no puede haber una TM que decida el problema de detención, porque hay al menos un caso que hemos construido explícitamente donde no hay Lógicamente posible respuesta. Recuerde que un decisor no puede emitir la respuesta incorrecta y debe emitir algo, pero en el caso que hayamos construido, ambas respuestas posibles son incorrectas.H A L T H A L $\mathrm{HALT}$$\mathrm{HALT}$$\mathrm{HALT}$

Estás discutiendo dos significados diferentes de "contradicción".

En su analogía, la máquina A y su modificación invertida se contradicen solo en el sentido de que sus salidas son siempre diferentes. (Por ejemplo, podrían implementar dos funciones de prueba en enteros, " x ≤ 5?" Y " x > 5?"). Eso es ciertamente una cosa que puede significar "contradicción" en el uso diario, pero no es lo que significa lógicamente. pruebas

En pruebas lógicas, significa algo más fuerte: algo que es simplemente imposible. Por ejemplo, una función que devuelve "verdadero" en todas las entradas de más de 5, y "falso" en todas las entradas de menos de 10 - eso es contradictorio en este sentido más fuerte, porque para, digamos, 7, su salida tendría que ser a la vez "verdadero" y "falso", pero esos no son lo mismo. El argumento de Turing muestra que el programa de detención es contradictorio en el sentido más fuerte: suponiendo que conduce a algo que es imposible o que ya se sabe que es falso.

Aquí hay otra prueba de que el problema de detención es indecidible. Decimos que un programa genera una cadena si se detiene y genera . (Si el programa nunca se detiene, entonces no emite ninguna cadena). Defina como la longitud de la cadena más larga que emite un programa C de longitud como máximo .x f ( n ) $x$$x$$f(n)$$n$

Supongamos que el problema de detención fuera decidible. Entonces puede calcularse mediante un programa en C:$f(m)$

En la entrada , ejecute todos los programas de C de longitud como máximo , y determine su salida; Devuelve la longitud de la salida máxima.$m$$m$

Eso significa que para cada , podemos escribir un programa que genera ceros. ¿Cuál es la longitud de ? Hay una plantilla de programa C fija, con un marcador de posición, que implementa ; el marcador de posición debe llenarse con la constante . Especificar tomacaracteres (aquí es la longitud de la representación decimal de ), donde . La plantilla toma un número fijo de caracteres, por lo que la longitud de es . Si elegimosP m f ( m ) + 1 P m P m m m | m | El | m | m | m | ≈ log 10 m T P m T + log 10 m m m = 2 T T + log 10 m ≤ m f ( m ) P m f ( m ) $m$$P_m$$f(m)+1$$P_m$$P_m$$m$$m$$|m|$$|m|$$m$$|m| \approx \log_{10} m$$T$$P_m$$T + \log_{10} m$$m$ suficientemente grande ( haría), tendremos , y entonces es al menos el tamaño de la salida de cadena por , es decir, . Hemos llegado a una contradicción.$m=2T$$T + \log_{10} m \leq m$$f(m)$$P_m$$f(m) \geq f(m) + 1$