loops - 为什么我们需要在图灵的停止证明中使用否定部分？

Question

例如，假设我有一台图灵机 H，它告诉我们程序和输入是否会停止。假设我们自己调用 H。它必须给出答案，所以如果它打印出“不停止”，那么它在技术上不是停止打印该语句吗？还是理论上总是会打印出“停止”？我很难将我的头脑完全围绕在自己身上调用 H ，没有否定，以及它会做什么。我明白为什么否定会导致矛盾，但我只是想知道以下情况是否也会导致矛盾。

谢谢！

Answer 1

你需要证明H不存在。您已经证明，应用于自身的 H 不能打印“不停止”。但是，正如您正确指出的那样，不排除打印“确实停止”的可能性。这并没有明显的矛盾。所以这个H对自身的应用不足以证明H不存在，我们需要使用其他技术。说这种情况不会导致矛盾是不正确的。如果你进一步探索它可能会。它只是不会立即这样做。