Confusion du problème d'arrêt

Question

montre que le problème suivant est résoluble. Deux programmes avec leurs intrants et la connaissance que exactement l'un d'entre eux s'arrête, déterminer qui s'arrête.

permet de p être un programme qui déterminera l'un des programmes sera arrêté.

P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

Puisque nous savons que exactement l'un d'entre eux sera arrêté, si 1 puis le programme X sera arrêté.Therwiae programme Y sera arrêté.

Ensuite, nous construisons un nouvel appel de programme D

D(X,Y){

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

         D will halt;

      else

         while(1)//D will not halt;

  }

Soyez un programme aritbrary.

donc si nous avons d (d (d, s)

si D va arrêter alors d ne sera pas arrêté

si D ne sera pas arrêté puis d une halte

Il importe une contradiction identique à la halte Problème.

Mais la question indiquait qu'elle est satisfaite.

Answer 1

Pour commencer avec une note latérale importante: Quelles sont les entrées pour $ x $ et $ y $ qu'ils vont s'arrêter? Vous devez spécifier une entrée spécifique pour les machines pour que la question soit bien définie (par exemple, la question pourrait être "donnée $ x, y $ où Exactement on se termine sur $ \ EPSILON $ , trouvez qui a été arrêté. "Ou peut-être," donné ... où exactement s'arrête toujours comme une entrée ... " )

Je vois ce qui vous confondre là-bas. Le problème est vraiment soluble: dans $ p $ émule à la fois $ x $ et $ y $ et répondez à celui qui s'est arrêté en premier.

Le problème de votre solution est qu'une entrée de $ p $ doit être $ x, y $ où exactement l'un d'entre eux s'arrête et l'autre ne le fait pas.

donc, une entrée appropriée à $ d $ doit être une entrée appropriée sur $ p $ . Notez maintenant que vous avez appelé $ d (d, s) $ . Pour vous assurer que $ d $ retournera une sortie correcte, nous devons avoir des entrées correctes: une seule des $ D $ < / span> ou $ s $ s'arrête! Mais ... si $ s $ arrête alors votre $ d $ aussi s'arrête et ce n'est pas une entrée appropriée à $ p $ , et donc pas non pas une entrée appropriée de $ D $ . Ainsi, vous ne pouvez pas compter sur la sortie de $ D (d, s) $ car il peut ne pas être correct