Confusione del problema di fermezza

Question

Mostra che il problema seguente è solvibile.Given Due programmi con i loro input e la conoscenza che esattamente uno di loro si ferma, determinare che si ferma.

Le consente di essere un programma che determinerà uno dei programmi verrà interrotto.

P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

.

Dal momento che sappiamo che esattamente uno di loro verrà interrotto, se 1 quindi il programma X verrà interrotto. Il programmaOtherwiae è fermato.

Quindi costruiamo una nuova chiamata di programma D

D(X,Y){

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

         D will halt;

      else

         while(1)//D will not halt;

  }

.

Lascia che sia il programma Aritbry.

quindi se abbiamo d (d, s)

Se D sarà fermi, allora D non si fermerà

Se D non si fermerà, allora D sarà fermato

Impiega una contraddizione come il problema di interruzione.

Ma la domanda ha dichiarato che è risolvibile.

Answer 1

Per iniziare con una nota importante Nota: quali sono gli ingressi per $ x $ e $ y $ che si fermeranno? È necessario specificare un ingresso specifico per le macchine affinché la domanda sia ben definita (ad esempio, la domanda potrebbe essere "data $ x, y $ dove Esattamente si termina su $ \ Epsilon $ , trova chi si fermò. "O forse," dato ... dove esattamente si ferma sempre su se stesso come un input ... " )

Vedo cosa ti ha confuso lì. Il problema è in effetti risolvibile: in $ p $ emulare sia $ x $ e $ y $ e rispondi a chi si fermò prima.

Il problema nella tua soluzione è che un ingresso a $ p $ deve essere $ x, y $ Dove esattamente Uno di loro si ferma e l'altro no.

Allora, un input appropriato a $ D $ deve essere un ingresso corretto per $ p $ . Ora nota che hai chiamato $ D (D, S) $ . Assicurarsi che $ D $ restituirà un'uscita corretta, dobbiamo avere input adeguati: solo uno dei $ D $ < / span> o $ s $ halts! Ma ... se $ s $ si ferma allora la tua $ d $ anche Si fermano e Non è un input appropriato per $ P $ , e quindi anche non un input appropriato a $ D $ . Pertanto non è possibile fare affidamento sull'output da $ D (D, S) $ come potrebbe non essere corretto