Confusão de travar problema

Question

Mostre que o seguinte problema é solucionável.Dado dois programas com seus insumos, e o conhecimento de que exatamente um deles pára, determinar que pára.

permite-P programa que determinar o programa será interrompido.

P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

desde que nós sabemos que exatamente um deles será interrompida,se 1, em seguida, o programa x será interrompido.Otherwiae programa de y será interrompido.

em seguida, construímos uma nova chamada do programa D

D(X,Y){

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

         D will halt;

      else

         while(1)//D will not halt;

  }

permite-S ser aritbrary programa.

Então, se temos D(D,S)

se D será interrompido, em seguida, D não vai parar

se D não será interrompido, em seguida, irá parar D

Ele impiles uma contradição mesmo como travar o problema.

A questão, porém, afirmou que é solúvel.

Answer 1

Para iniciar com uma importante observação:o que são as entradas para $X$ e $Y$ que eles vão parar em?você precisa especificar uma entrada específica para as máquinas, para que a questão seja bem-definido (por exemplo, a causa pode ser "dada $X,Y$ onde, exatamente, um termina em $\epsilon$, encontrar quem pode parar." Ou, talvez, "dado ...onde, exatamente, um sempre pára em si mesmo como uma entrada...")

Eu vejo o que poderiam confundi-lo lá.O problema é, de fato, resolvido:no $P$ emular $X$ e $Y$ e a resposta de quem parou primeiro.

O problema na sua solução, que é a entrada para $P$ deve ser $X,Y$ onde exatamente um deles é interrompida, e os outros não.

Assim, uma entrada adequada para $D$ deve ser uma entrada adequada para $P$.Agora, observe o que você chamou de $D(D,S)$.Para certificar-se de que $D$ irá retornar uma saída correta, devemos ter bom entradas:apenas um dos $D$ ou $S$ pára!Mas...Se $S$ pára, em seguida, seu $D$ também pára e esta não é uma entrada adequada para $P$, e , portanto, também não é uma entrada adequada para $D$.Assim, você não pode confiar na saída de $D(D,S)$ como pode não estar correto