Facts About David Hilbert
没错, 这篇文章其实是 Cantor, Gödel, Turing 这个主题. 我发现只要关于他们的东西都很容易让我看 high..
最近在看那本 The Annotated Turing. 书中第三章以 David Hilbert 为主线, 介绍了 20 世纪初的几十年里数理逻辑与集合论的发展. 想一想的话, Hilbert 的确是将 Cantor, Gödel, Turing 联系起来的关键人物, 然而这段历史我以前知道的并不细致, 而且关于 Hilbert's Program, Hilbert's Problems 的故事各个地方说的都乱七八糟的自己也不清楚了, 于是做个记录.
-
Hilbert 自 1898 年前后起开始对几何基础感兴趣, 应该是受到当时非欧几何潮流的影响, 1899 年出版了巨著几何基础, 将几何学的数学基础用严格的方式奠定. Peano 的自然数公理化提出于此前十年.
-
1900-08-08, 巴黎, 第二届国际数学家大会.
在此前, Minkowski 就曾建议 Hilbert:
最吸引人的莫过于展望未来......
如果你选择了这样的主题, 人们在数十年后还会对你的演讲津津乐道
Hilbert 就以下面这段话, 开始了他的著名演讲. 那 23 个问题, 在现场由于时间关系只说了 10 个.
Who among us would not be happy to lift the veil behind which is hidden the future; to gaze at the coming developments of our science and at the secrets of its development in the centuries to come?
What will be the ends toward which the spirit of future generations of mathematicians will tend?
What methods, what new facts will the new century reveal in the vast and rich field of mathematical thought?
这学期的数学史课上, 江宁老师谈到 Hilbert 问题时曾经与 Clay 的 Millennium Prize 相比, 毕竟要说有什么著名的数学问题列表的话, 恐怕多数人最先想到的都是这两个. 相比起来, Millennium Prize 不够深刻, 问题偏应用向, 而且如果不是有 100 万的话恐怕名气也不会如此. Hilbert 作为最后一个数学全才 (Klein 好像也有这个名号..), 其提出的问题对数学发展的指导的确空前绝后了.
不过即使如此, 20 世纪数学最牛 B 的发展, 包括 Gödel 对他雄伟计划的摧毁, 计算机出现, 和微分几何, 微分拓扑, 代数拓扑, 代数几何这些东西走向数学研究的前沿, 都不是那时的他所能够预料到的.
这场演讲与 Cantor, Gödel, Turing 有什么关系呢? 恰恰就是这场演讲的第一个问题, 与最后一个问题, 把一切连到了一起:
The continuum hypothesis :
There is no set whose cardinality is strictly between that of the integers and that of the reals.
Entscheidungsproblem:
Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.
第一个问题, Cantor 连续统假设. 1963 年, Paul Cohen 使用 Forcing Method 证明了这个问题恰恰是 Gödel 定理所暗示的那种, 在 ZFC 中即无法被证明也无法被证否的命题.(其实 Gödel 在 1940 年就已经证明了它无法被证否)
第十个问题, Diophantine 方程可解判定性问题. 至此, "判定" 这个词, 与 "算法" 的概念, 出现在数学历史中. 虽然这个问题本身最终由别人解决, 但 Gödel1931 与 Turing1936 是它们的奠基者, 并且这两个概念的出现, 导致了后来对整个数学系统可判定性的思考.
-
1901 年, Russell 发现了 Russell's Paradox, 给出了 Frege 集合基础中的悖论. 为了修复这个悖论, 1908 年 Zermelo 提出了 "首个公理化的集合论", 最终发展成了今天的 ZFC. 然而 Russell 当时并未接受, 用了一套自己发展出的不太靠谱的修复方法, 与 Whitehead 一起, 在 1910-1913 年间出了三大本的 Principia Mathematica
-
Hilbert 开始了对逻辑的兴趣. 1917 年 9 月 11 日, 瑞士, Hilbert 在一次以 "Axiomatic Thought" 为题的演讲中提出了 Hilbert's Progarm, 他希望数学被彻底的形式化, 并且还要是公理独立的, 一致的, 完备的, 可判定的.
-
1921 年, Hilbert 的助手 Behmann 在一份关于 Entscheidungsproblem 的手稿中写到:
It is of fundamental importance for the character of this problem that only mechanical calculations according to given instructions, without any thought activity in the stricter sense, are admitted as tools for the proof. One could, if one wanted to, speak of mechanical or machinelike thought. (Perhaps one could later let the procedure be carried out by a machine)
想象一下, 对于判定性这样一个数学问题, 终于有人把它同 "mechanical", "machinelike thought" 这样的词联系到了一起, 这是多么革命性的思想. 这一想法终于在 15 年后由 Turing 得以完成.
-
1922-1923 年, Hilbert 在 Gottingen 教逻辑学. 1928 年, 他的助手 Ackermann 整理其讲义, 出版了一本小书, 名为数理逻辑原理. Gödel 恰恰是这本书的早期读者之一, 1929 年, Gödel 在其博士论文中证明了书中的一个问题, 即一阶谓词逻辑的完备性. Hilbert 离他的雄伟目标又进了一步.
-
1930 年 9 月 8 日, Hilbert 的退休演讲上, 他乐观的说出那句话:
Wir müssen wissen. Wir werden wissen.
然而就在这前一天, 9 月 7 日, 同一所城市里, Gödel 宣布证明了支持算术的一阶谓词逻辑系统是不完备的. 一年之后他发表了神の Gödel1931, "震撼了 20 世纪数学界的天空".
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
英文版:On formally undecidable propositions of Principia Mathematica and related systems I
听说到 Gödel 结果的 Hilbert"有些愤怒".
Gödel 的结论解决了完备性与一致性的问题, 但给可判定性似乎还留下了空间. 判定真命题是没有希望了, 但会不会存在一种算法, 能够判定一个命题的可证明性呢?
-
Turing 很可能是在 1935 年夏天开始对判定性问题感兴趣. 次年 4 月, 他提交了 Turing1936 的草稿. 几乎同时, Alonzo Church 也给出了判定性不可解的证明. 之后, Turing 补充了一份附录, 说明了自己工作与 Church 工作的等价性, 年底, 神の Turing1936 发表.
On computable numbers, with an application to the Entscheidungsproblem
次年, Church 在一篇评论中首次使用 "Turing Machine" 一词.
人类迎来了崭新的时代.