停止问题的困惑

Question

表明以下问题是可解释的。从其输入的两个程序以及恰好其中一个停止的知识，确定哪个停止。

让p是确定一个程序将停止的程序。

P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

.

因为我们知道它们中的一个将被停止，如果1那么程序x将被暂停。将停止。

然后我们构建一个新的程序调用d

D(X,Y){

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

         D will halt;

      else

         while(1)//D will not halt;

  }

.

让s成为aritbrary程序。

所以如果我们有d（d，s）

如果d会停止，则d不会停止

如果d不会停止，则d将停止

它意外矛盾与停止问题相同。

但问题表示它是可解释的。

Answer 1

以重要的侧面注：和 $ y $ 他们会停止吗？您需要为机器指定特定的输入，以便是定义的问题（例如，问题可以“给定 $ x，y $ 在哪里正是一个终止于 $ \ epsilon $ ，找到谁停止了。“或许，”给定......恰好一个总是将自己停止作为一个输入......“ ）

我看到你在那里混淆了什么。问题确实是可解释的：在 $ p $ 中，模拟 $ x $ 和 $ Y $ 并回答首先停止的人。

解决方案中的问题是输入到 $ p $ 必须是 $ x，y $ 其中完全其中一个停止，另一个没有。

因此，对 $ d $ 必须是一个正确输入到 $ p $ 。现在注意您称为 $ d（d，s）$ 。要确保 $ d $ 将返回正确的输出，我们必须具有正确的输入：只有一个 $ d $ < / span>或 $ s $ 停止！但是......如果 $ s $ 停止，那么你的 $ d $ 也停止和这不是一个正确输入 $ p $ ，因此也不是 $ d $ 。因此，您无法依赖于 $ d（d，s）$ ，因为它可能不正确