Prueba de la indecidibilidad del problema de detención

Tengo problemas para comprender la prueba de la indecidibilidad del problema de detención.

Si devuelve si el programa a se detiene o no en la entrada b , ¿por qué tenemos que pasar el código de P para a y b ?$H(a,b)$$a$$b$$P$$a$$b$

¿Por qué no podemos alimentar con P y alguna entrada arbitraria, por ejemplo, x ?$H()$$P$$x$

La prueba tiene como objetivo encontrar una contradicción. Debe comprender cuál es la contradicción derivada, para comprender por qué se utiliza como una entrada para sí mismo. La contradicción es, informalmente: si tenemos una máquina H (a, b) que decide "a acepta b", entonces podemos construir una máquina que acepte máquinas que no se aceptan a sí mismas. (Leer que un par de veces hasta que lo haga.) La máquina que se muestra en la imagen - llamémoslo M - M ( P ) = no P no acepta ⟨ P ⟩ ?$P$$M$$M(P) =$$P$$\langle P \rangle$

La contradicción ocurre cuando se pregunta: Qué aceptar ⟨ M ⟩ ? Intenta resolver las dos opciones para ver cómo hay una contradicción.$M$$\langle M \rangle$

acepta ⟨ M ⟩ si y sólo si M no acepta ⟨ M ⟩ ; Esto es claramente una contradicción.$M$$\langle M \rangle$$M$$\langle M \rangle$

Esta es la razón por la cual es esencial que la prueba ejecute sobre sí misma, no alguna entrada arbitraria. Este es un tema común en las pruebas de imposibilidad conocidas como argumentos diagonales.$P$

Ignora la imagen por un momento; Lo veremos en breve. Se supone que el programa es un probador de alto: cuando le damos a H una entrada de un programa a (piense en a como la lista de un programa) y cualquier cosa para b , H ( a , b ) actúa de la siguiente manera$H(a, b)$$H$$a$$a$$b$$H(a, b)$

1. Si el programa representado por detiene cuando se le da b como entrada, H ( a , b ) responderá "sí". Por otro lado, si el programa descrito por a se ejecuta para siempre cuando se le da la entrada b, entonces H ( a , b ) responderá "no".$a$$b$$H(a, b)$$a$$b$$H(a, b)$
2. Es importante destacar que el programa siempre se detendrá y dará la respuesta correcta para cualquier par ( a , b ) .$H$$(a, b)$

El argumento de que es imposible de construir se basa en la acción de un programa "perverso" particular, P , uno que usa H como subrutina. P toma como entrada una lista de cualquier programa, x , y hace lo siguiente:$H$$P$$H$$P$$x$

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

No es difícil ver eso

se detendrá si y solo si el programa x se ejecutará para siempre cuando se le dé su propia descripción como entrada.$P(x)$$x$

Hasta ahora todo bien: sin duda será un programa siempre que su subrutina H sea ​​un programa.$P$$H$

$P$$p$$P$

$P(p)$$P(p)$

$H$$(p, p)$$H$$H$

Prueba una prueba más bonita con animaciones. Y dado que los mensajes deben contener algo más que un enlace a un sitio, esta es la respuesta a su pregunta.

Primero, recordemos cómo funciona la prueba de la no existencia del oráculo de detención. Demostramos que dado cualquier candidato Hpara un oráculo de detención, hay un programa Py una entrada apara los cuales Hno se puede predecir correctamente lo que P(a)hace.

Teorema: Sea Hcualquier programa que tome dos entradas y siempre devuelva halto loop. Luego, existe un programa Qy una entrada aque se Q(a)detiene si, y solo si, H(Q,a)regresa loop.

Prueba. Considera el programa

program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

Deje Q = Py a = P. Ya sea H(Q,a) = halto H(Q,a) = loop:

• si H(Q,a) = haltentonces Q(a)(que es justo P(P)) se ejecuta para siempre según la definición de P.
• si H(Q,a) = loopentonces se Q(a)detiene por la definición de P.

QED

Usted preguntó por qué lo consideramos en H(P,P)lugar de H(P,X)otro X. ¡La respuesta obvia es "porque H(P,P)es lo que hace que la prueba funcione"! Si H(P,X)usabas algo arbitrario X, entonces te quedarías atascado. De hecho, la prueba se vería así:

Prueba rota Considera el programa

program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

Let Q = Py a = Xpara algunos arbitrarios X. Ya sea H(Q,X) = halto H(Q,X) = loop:

• supongamos H(Q,X) = haltque no podemos decir qué P(X)hace, porque si se P(X)detiene depende de lo que H(X,X)regrese. Estamos atascados. Sin embargo, si supiéramos eso P(X)y X(X)somos iguales, podríamos avanzar. (Entonces, realmente deberíamos tomar X = P).
• si H(Q,a) = loopentonces estamos atascados nuevamente, y nos despegaríamos si X = P.

No QED

Espero que esto muestre que debemos considerar H(P,P)para que nuestra idea funcione.

El resultado de la prueba es esta analogía:

$P$$_{(P)}$$P^{\prime}$$_{(P^{\prime})}$$P$$_{(P)}$$_{(P)}$$_{(P)}$

$_{(P)}$$_{(P^{\prime})}$