艾伦·图灵在1936年迈出了关键一步，证明不完备性是自然且普遍存在的，他论证了不存在通用的程序来判断一个独立的计算机程序是否会最终停止运行。
为了证明这个结论，我们假设我们想要证明的结论的反面是成立的。 也就是说，假设存在一个通用程序 H，它可以判断任何给定的计算机程序是否会停止运行。 从这个假设出发，我们将推导出矛盾。 这就是所谓的归谬法证明。
因此，假设存在 H，我们可以构建以下程序 P，它使用 H 作为子程序。 程序 P 知道自身的大小（以比特为单位，N）——P 中肯定有空间容纳数字 N——然后使用 P 包含的 H，P 会检查所有大小不超过 N 比特 100 倍的程序，以查看哪些程序会停止运行，哪些不会。 然后 P 运行所有停止运行的程序，以确定它们产生的输出。 这将精确地是复杂性不超过 N 比特 100 倍的所有数字对象的集合。 最后，我们的程序 P 输出不在此集合中的最小正整数，然后 P 自身停止运行。
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。 通过购买订阅，您正在帮助确保未来能够继续讲述关于塑造我们当今世界的发现和想法的具有影响力的故事。
因此，P 停止运行，P 的大小为 N 比特，并且 P 的输出是一个整数，该整数无法由大小小于或等于 N 比特 100 倍的程序生成。 但是 P 刚刚将此整数作为其输出生成，并且它太小而无法做到这一点，因为 P 的大小仅为 N 比特，远小于 N 比特 100 倍。 矛盾！ 因此，用于判断程序是否会停止运行的通用程序 H 不可能存在，因为如果存在，那么我们实际上可以使用 H 构建这个自相矛盾的程序 P。
最后，图灵指出，如果存在一种万物理论，它总是能够让你证明一个单独的程序会停止运行，或者证明它永远不会停止运行（无论哪种情况属实），那么通过系统地运行所有可能的证明，你最终可以判断个别程序是否会停止运行。 换句话说，我们可以使用这个理论来构建 H，而我们刚刚证明 H 不可能存在。 因此，对于停机问题，不存在万物理论。
类似的推理表明，对于所有长度不超过 N 比特的程序，没有哪个长度明显短于 N 比特的程序可以解决图灵停机问题。