1707629918
1707629919
1707629920
1707629921
1707629922
霍金的派对：从科学天地到数码时代 [:1707629762]
1707629923
霍金的派对：从科学天地到数码时代 第一部分 科学天地
1707629924
1707629925
霍金的派对：从科学天地到数码时代 [:1707629763]
1707629926
计算机与数学证明(1)
1707629927
1707629928
1707629929
1707629930
1707629931
自20世纪30年代起，有位名叫“布尔巴基”（Nicolas Bourbaki）的数学家崭露了头角，后来人们知道，他其实不是一个人，而是一群数学家的笔名。用笔名在科学界是较少见的，但也并非绝无仅有，比如当今数学界有个叫“艾卡德”（Shalosh B．Ekhad）的家伙发表了几十篇论文，也并不是一个人，甚至不是人，而是计算机。“艾卡德”虽远没有“布尔巴基”出名，象征意义却不容忽视，因为其“导师”——以色列数学家蔡尔伯格（Doron Zeilberger）——坚持让计算机独立署名，乃是为显示其在数学中日益重要的作用。
1707629932
1707629933
计算机在像物理那样的经验科学中的作用早已被广泛认可，一篇物理论文哪怕全部演算都靠计算机，也不会引起非议。数学却不同，它对严谨性的要求在物理之上，结果则不像物理那样受观测检验，因此特别注重推理的步骤。德国数学大师克莱因（Felix Klein）在名著《数学在19世纪的发展》中曾这样描述数学：“不管什么人，想要进入它，就必须在自己心里，依靠自己的力量，一步一步把它的发展再现一次。”计算机一介入数学证明，就明显破坏了克莱因的描述。
1707629934
1707629935
但计算机介入数学证明的势头却颇有些难以阻挡。早在其问世不久的20世纪50年代，一些美国数学家——其中包括华裔数学家王浩——就用计算机证明了英国哲学家罗素（Bertrand Russell）和怀特黑德（Alfred North Whitehead）的名著《数学原理》（Principia Mathematica）中一阶逻辑部分的全部定理；另一些数学家——其中包括中国数学家吴文俊——则用计算机证明了许多几何定理。而最轰动的则是1976年，美国数学家阿佩尔（Kenneth Appel）和德国数学家黑肯（Wolfgang Haken）用计算机辅助证明了四色定理（four color theorem）——一个从未被常规手段证明过的定理。
1707629936
1707629937
计算机介入数学证明引起了很多数学家的不安，因为在计算机领域中，像Windows、MacOS那样的操作系统，像Mathematica、Maple那样的应用软件都不是开放源代码的，从而在原则上就不是数学家所能检验的。更糟糕的是，即便是原则上可以检验的部分，比如直接介入数学证明的那部分程序，数学家通常也没什么兴趣去检验，因为那些程序所做的通常是运算量巨大而逻辑结构死板的工作，检验起来往往既学不到数学，也得不到启示，实在是味同嚼蜡。这种兴趣匮乏的一个后果，就是数学证明中的计算机部分往往会拖整个证明的后腿。这方面一个著名的例子是1998年美国数学家黑尔斯（Thomas Hales）向著名刊物《数学年刊》提交的一个有关开普勒猜想（Kepler conjecture）的证明。该证明包含了约250页的文稿及10万行左右的计算机程序。结果等了4年也没人检验他的程序，等了7年文稿部分才得以发表，但整个证明迄今未被公认。无奈之下，黑尔斯自2003年起开始研发一个能让计算机检验此类证明的系统。但据他估计，该系统若由一个人研发，约需20年的时间，看来是要“等到花儿也谢了”。而且该系统本身就是计算机程序，从而首先得接受检验。
1707629938
1707629939
计算机介入数学证明引发的一个重要问题是：数学证明的明天会怎样？对此人们众说纷纭。一些人认为，随着数学研究的不断深入，计算机的介入将日益显著，不用计算机做数学将如同不穿鞋子跑马拉松。比如蔡尔伯格就表示，人类正日益接近自身证明能力的极限，今天的许多数学研究已没多大意思，之所以仍有人做，只是因为唯有那些东西才是人类还能直接胜任的。他预期，随着计算机能力的快速增长，再过二三十年，大多数研究都将可以由计算机来做。它们不仅能证明数学定理，甚至可以发现数学定理。另一些人则坚信，数学仍将是他们熟悉的数学，计算机至多只能起辅助作用。就不太遥远的将来而言，我更倾向于后一种看法，因为数学证明中很多精妙的东西恐怕在很长时间内都不是计算机能够胜任的，比如拿费马大定理来说，它是一个有关自然数的命题，其证明——据我们所知——却要用到大量远远超出自然数范畴的高深数学，如果我们把命题及自然数的公理输入计算机，它几乎要自行重建数学大厦的很大一部分结构才有可能给出证明，这在我看来绝不是二三十年后的计算机能够胜任的。
1707629940
1707629941
退一万步说，假如真有前面那些人所说的那一天，很多数学家依然乐观地认为他们有事可做，因为他们认为，那时候的数学将是找出并研究那些无法用计算机来做的东西！
1707629942
1707629943
(1) 本文发表于《科学画报》2013年第12期（上海科学技术出版社出版）。
1707629944
1707629945
1707629946
1707629947
1707629948
霍金的派对：从科学天地到数码时代 [:1707629764]
1707629949
霍金的派对：从科学天地到数码时代 物理学是困难的——数学家的证言？(1)
1707629950
1707629951
1707629952
1707629953
1707629954
2012年3月，著名物理学刊物《物理评论通讯》（Physical Review Letters）发表了西班牙马德里大学（Complutense University of Madrid）的数学家丘比特（Toby S．Cubitt）及同事的一项有趣的研究，其结论被许多媒体描述为：物理学是困难的。
1707629955
1707629956
对多数人来说，这也许没什么新鲜的，因为物理学一向就被认为是困难的。不过，当普通人说“物理学是困难的”时，如果我们追问：什么叫做“困难的”？如何证明“物理学是困难的”？多半会被视为抬杠。但同样的话成为数学家的证言时，这些就不再是抬杠，而变成非常有趣味的问题了。
1707629957
1707629958
那么就让我们探究一下其中的趣味吧。
1707629959
1707629960
物理学是困难的——数学家的证言？霍金的派对——从科学天地到数码时代00[]00先说说“困难的”。数学家对数学问题——确切地说是所谓的判定问题（decision problem）——的困难度有着严格的分类，其中最常用的两个类别是P和NP，前者是在多项式时间（polynomial time）内能找到答案的问题；后者则是在多项式时间内能验证答案的问题。这其中“多项式时间内”指的是用理想计算机——也叫图灵机（Turing machine）——为工具所需花费的时间随输入信息数量的增加不快于某个多项式函数。在这两个类别中，P是困难度最低的，NP则由于只对验证答案的时间作了限定，从而有可能包含某些无法在多项式时间内找到答案——即比P问题更困难——的问题。为了方便起见，数学家们将NP问题中最困难的称为NP完全（NP complete）问题。而“困难的”这一概念，它的全称乃是“NP困难的”（NP hard），指的是起码跟NP完全问题一样困难（但不一定属于NP这一类别）。限于篇幅，对“最困难”及“一样困难”这两个概念我们只得割爱了，但请相信我，它们也是有严格定义的，并非偷梁换柱。
1707629961
1707629962
接下来说说如何证明“物理学是困难的”。丘比特等人认为，很大一部分物理学所研究的乃是物理体系的状态演化，其形式类似于数学上的马尔可夫过程（Markov process），特点是每个时刻的状态都可以通过一个所谓的转移矩阵，从前一时刻的状态中计算出来。利用这种类似性，研究物理体系的状态演化可以抽象为一个数学问题，即通过实验数据确定转移矩阵。而这一数学问题——丘比特等人证明了——是跟一个已被证明为是“困难的”的数学问题一样困难的。这样，他们就证明了“物理学是困难的”——当然，如前所述，这是媒体对他们结论的描述，丘比特等人原始论文的措辞要严密得多。
1707629963
1707629964
由于是第一次有人对“物理学是困难的”这一含义模糊的老生常谈给出精确描述及证明，丘比特等人的研究引起了很多人的兴趣，其中既有对结论的兴趣，也有对日常概念精确化的好奇。有些媒体则很替物理学家们高兴，因为“物理学是困难的”意味着物理学家们不必担心计算机能抢他们的饭碗。
1707629965
1707629966
不过，将丘比特等人的研究结论描述为“物理学是困难的”其实是有一定误导性的。
1707629967