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

Question

例如，假设我有一台图灵机 H，它告诉我们程序和输入是否会停止。假设我们称 H 为自身。它必须给出一个答案，所以如果它打印出 "does not halt" 那么它在技术上不会停止打印该语句吗？还是理论上总是打印出 "does halt"？我无法全神贯注地完全根据自身调用 H，没有否定，以及它会做什么。我明白为什么否定会导致矛盾，但我只是想知道以下情况是否也会导致矛盾。

谢谢！

Answer 1

你需要证明H不存在。您已经证明应用于自身的 H 无法打印 "does not halt"。但是，正如您正确指出的那样，不排除打印 "does halt" 的可能性。这没有明显的矛盾。所以这种H对自身的应用并不足以证明H不存在，还需要用到其他的技巧。说这种情况不会导致矛盾是不正确的。如果你进一步探索它可能会。它只是不会立即这样做。