¿Hay alguna prueba de la indecidibilidad del problema de detención que no depende de autorreferencia o diagonalización?

Esta es una pregunta relacionada con esta . Poniéndolo de nuevo en una forma mucho más simple después de mucha discusión allí, se sintió como una pregunta totalmente diferente.

La prueba clásica de la indecidibilidad del problema de detención depende de demostrar una contradicción cuando se trata de aplicar un hipotético HALT decider a sí mismo. Creo que esto es sólo denota la imposibilidad de tener un HALT decisivo que decide si sí se parará o no, pero no da ninguna información más allá de que alrededor del decidibilidad de detención de los otros casos.

Entonces la pregunta es

¿Existe alguna prueba de que el problema de detención sea indecidible que no dependa de mostrar que HALT no puede decidir por sí mismo, ni depende del argumento de diagonalización?

Edición pequeña: me comprometeré con la redacción original de la pregunta, que es pedir una prueba que no dependa en absoluto de la diagonalización (en lugar de solo requerir que no dependa de la diagonalización que depende de HALT).

Sí, existen tales pruebas en la teoría de la computabilidad (también conocida como teoría de la recursividad).

Primero puede mostrar que el problema de detención (el conjunto ) se puede usar para calcular un conjunto que es 1-genérico, lo que significa que, en cierto sentido, cada hecho sobre se decide por un finito prefijo de . Entonces es fácil demostrar que dicho conjunto no puede ser computable (es decir, decidible). G ⊆ N Σ 0 1 G G $0'$$G\subseteq\mathbb N$$\Sigma^0_1$$G$$G$$G$

Podríamos reemplazar 1 genérico aquí por 1 aleatorio, es decir, aleatorio Martin-Löf , para el mismo efecto. Esto utiliza el teorema de base baja de Jockusch-Soare .

(Advertencia: uno podría considerar simplemente mostrar que calcula Chaitin , que es 1 aleatorio, pero aquí tenemos que tener cuidado sobre si la prueba de que es 1 aleatorio se basa en que el problema de detención es indecidible. Por lo tanto, es más seguro usar el teorema de base baja).Ω$0'$$\Omega$$\Omega$

Publicado de mi comentario según la solicitud:

Comience con la observación de que hay problemas indecidibles (argumento de cardinalidad simple) y, además, que existe un problema indecidible P que tiene una TM M que reconoce a sus miembros (pero que no puede terminar en los no miembros). Ahora, resolver HALT (M) te da un decisor para P. Primero verificamos si M se detiene en x. Si lo hace, lo ejecutamos y devolvemos lo mismo que M. De lo contrario, rechazamos, ya que M se detiene en cada miembro de P. Esto ahora es una contradicción ya que asumimos que P era indecidible.

Nota: Aclaró que estaba buscando un argumento que evitara la diagonalización utilizando HALT directamente, no un argumento que evitara la diagonalización por completo.

EDITAR: Este argumento está atascado. ¿Puede mostrar directamente que RE - REC no está vacío, además de mostrar que HALT está allí?

Otro póster aludió a esto (refiriéndose a Chaitin), pero puede usar la paradoja de Berry para demostrar que el problema de detención es indecidible. Aquí hay un breve bosquejo de la prueba:

Deje que HALT sea una máquina que decida si alguna máquina M se detiene en la entrada I. Demostraremos que HALT no logra detenerse en una entrada en particular, lo que demuestra que no puede decidir el idioma.

Considere la siguiente función f:

f (M, n) = a, donde a es el número entero positivo más pequeño no computable por la máquina M en cualquier entrada I con | I | <n

Suponiendo que HALT es una función computable, f también es una función computable; simplemente simule HALT (M, I) para cada máquina M e ingrese la cadena I con una longitud de I menor que n. Si la simulación se detiene, simule M (I) y registre cuál es la salida, y encuentre la salida más pequeña a que no salga por ninguno de los pares M, n.

Ahora, mostramos que f no es computable: considere f (f, 10000000 * | f | +10000000). Sea lo que sea que produzca, debería ser un número entero (positivo) que no sea computable por la máquina que calcula f en la entrada I con una longitud menor que la dada ... y, sin embargo, acabamos de generar un número entero con fy mucho más breve entrada.

Por lo tanto, f no es computable, por lo que nuestra suposición de que HALT era computable es falsa. No creo que esta prueba haga uso de la diagonalización.

$\{W_e\}_{e=1}^{\infty}$$f$$e$$W_e = W_{f(e)}$$0$$f$$e$$0$$W_e$$0$$e$$W_e(0)$$W_{f(e)}(0)$