Confusión de detener el problema

Question

Muestra que el siguiente problema es solvable. Generen dos programas con sus insumos y el conocimiento de que exactamente uno de ellos se detiene, determina qué se detiene.

Vamos a ser un programa que determine que se detenga uno de los programas.

P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

Dado que sabemos que exactamente uno de ellos se detendrá, si se detenga 1, luego se detendrá el programa X.OTHERWIAE PROGRAM Y se detendrá.

Luego construimos una nueva llamada de programa D

D(X,Y){

     if(P(X,Y) == 2)

         D will halt;

      else

         while(1)//D will not halt;

  }

vamos a ser un programa aritrario.

así que si tenemos D (D, S)

si D se detendrá entonces D no se detendrá

si D no se detendrá entonces, se detendrá

impila una contradicción igual que el problema de detención.

Pero la pregunta declaró que es solucionable.

Answer 1

Para comenzar con una nota lateral importante: ¿cuáles son las entradas para $ x $ y $ y $ ¿Que se detendrán? Debe especificar una entrada específica para las máquinas para que la pregunta esté bien definida (por ejemplo, la pregunta podría ser "dada $ x, y $ donde Exactamente uno termina en $ \ epsilon $ , encuentra quién se detuvo ". O tal vez," Dado ... Donde exactamente uno siempre se detiene en sí mismo como una entrada ... " )

Veo lo que te confundió allí. El problema es de hecho solucible: en $ p $ emular tanto $ x $ y $ y $ y responde a quien se detuvo primero.

El problema en su solución es que una entrada a $ p $ debe ser $ x, y $ Donde exactamente uno de ellos se detiene, y el otro no.

Por lo tanto, una entrada adecuada para $ d $ debe ser una entrada adecuada para $ P $ . Ahora aviso que llamaste $ d (d, s) $ . Para asegurarse de que $ d $ devolverá una salida correcta, debemos tener entradas adecuadas: solo uno de $ d $ < / span> o $ s $ detenciones! Pero ... si $ s $ detiene entonces su $ d $ también se detiene y Esta no es una entrada adecuada para $ P $ , y por lo tanto, tampoco es una entrada adecuada para $ D $ . Por lo tanto, no puede confiar en la salida de $ d (d, s) $ , ya que puede no ser correcto