库尔特·哥德尔

概述

奥地利-美国逻辑学家、数学家（1906–1978），20世纪最具影响力的逻辑学家之一。1931年发表两条不完备定理，彻底改变了人类对数学基础的理解，终结了 Hilbert 形式化纲领的核心期望。

关键内容

不完备定理（1931）

年仅25岁时发表的两条定理，对数学基础产生深远影响：

第一不完备定理：任何足够强大的、一致的形式系统中，都存在既不能被证明也不能被反驳的命题。换言之，数学真理的范围永远超出任何单一形式系统的证明能力。
第二不完备定理：这样的系统无法证明自身的一致性。

证明方法：Godel 构造了一个"自指"的命题——一个本质上在说"这个命题在本系统中不可证"的数学语句。如果系统是一致的，这个命题就既不能被证明也不能被反驳。这一精巧的构造使用了 Godel 编码（将数学语句编码为自然数），使得形式系统能够"谈论自身"。

与 Hilbert 纲领的关系

Godel 的定理粉碎了 Hilbert 纲领中关于完备性和一致性的期望，但没有直接回答判定问题（Entscheidungsproblem）。不完备定理说的是"有些真命题无法被证明"，但判定问题问的是"是否存在一种方法能判定任意命题的真假"——这是一个关于算法存在性的问题，而非关于可证性范围的问题。理论上，一个命题即使在某个系统中不可证，也许仍然有某种机械方法能判定它是真是假。因此，判定问题在1931年后仍然悬而未决，直到1936年才被 Church 和 Turing 独立解决。

一般递归函数

Godel 与 Kleene 共同发展了一般递归函数（general recursive functions）理论，这是可计算性的另一种形式化定义。后来被证明与图灵机和λ 演算完全等价，共同构成了Church-Turing 论题的经验基础。

其他贡献

连续统假设：证明了连续统假设（CH）与 ZFC 公理系统的一致性（1940）
广义相对论：在普林斯顿高等研究院期间，发现了 Einstein 场方程的一个旋转宇宙解（Godel 宇宙），其中存在闭合类时曲线，引发了关于时间旅行可能性的哲学讨论
与 Einstein 的友谊：在普林斯顿高等研究院与 Einstein 成为密友，两人经常一起散步

来源

raw/books/计算机科学/01-turing-on-computable-numbers.md