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:

最吸引人的莫过于展望未来......

如果你选择了这样的主题, 人们在数十年后还会对你的演讲津津乐道

Hermann Minkowski

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?

David Hilbert1900

这学期的数学史课上, 江宁老师谈到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.

Hilbert's 1st Problem

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.

Hilbert's 10th Problem

第一个问题, 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.
HilbertKönigsberg

然而就在这前一天, 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"一词.


人类迎来了崭新的时代.

Comments