首页 >> 数学 >> 计算机科学 >> 文章

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

“我要借了阿尔志跋绥夫的话问你们:‘你们将黄金时代的出现豫约给这些人们的子孙了,但有什么给这些人们自己呢?’”

——鲁迅

黄金时代

但波斯特并没有能够亲眼在《数学年报》看到他和克林的这篇论文。

双相情感障碍一直困扰着他,即使每天只工作三小时,即使用尽办法平伏情绪,每得到一些新的数学结果,这些发现和创造都让他激动不已,处于症状发作的边沿。对于数学家来说,这可能是最扭曲最恶毒的诅咒。数学家的使命在于发现新的数学,这种发现必然带来的喜悦,对于波斯特来说,却会危及他为了发现数学所必须的清醒头脑。

在1954年初,又一次的发作将他带到了纽约的一家精神病院。当时治疗精神疾病的主要疗法有两种,波斯特接受的是电休克疗法,而同样受精神疾病困扰的另一位数学家纳什接受的则是胰岛素休克疗法。电休克疗法在当时还很原始,虽然以相当高的症状缓解率得到了医生的青睐,但原始的疗法过程痛苦可怕,也有一定的副作用。

在1954年4月21日,波斯特接受了又一个疗程的电休克治疗。在他不停抽搐之时,他的心脏失去了控制。

他没有挺过去。

刊登着他和克林的论文的《数学年报》,则是在5月出版,只差不到一个月。

来自Wikimedia

来自Wikimedia

除了波斯特以外,可计算性理论这个领域的其他开拓者,哥德尔、图灵、丘奇这些先驱,他们的结局又如何呢?

由于二战即将爆发,哥德尔在1939年偕同家人移居到了普林斯顿,恰好在图灵回英国之后。之后,他一直作为普林斯顿的教授活跃在数理逻辑学界。但在四十年代后期,他的关注点渐渐从数理逻辑转移到了哲学,也不再发表他的数学工作。可以说,这就是他的数学生涯的终点。而他的人生的终点要等到近四十年之后。在晚年,他的心理变得不稳定,总是怀疑别人要毒害他。在他的妻子因病入院六个月时,他竟然不接受任何人的食物,活活饿死在普林斯顿的医院里。

图灵在1939年博士毕业后回到剑桥,旋即被英国军方聘用,专注破译德军密码,为二战胜利立下了汗马功劳。在战争结束后,他尝试制造一台计算机,但在英国政府的不作为,被在美国的冯·诺依曼抢了先。除此之外,图灵还提出了有关人工智能的图灵测试,并且一直思考前沿的数学问题。作为一名同性恋者,在被警方发现之后,图灵被迫接受治疗。最后在1954年6月8日,他的生命永远地终止了,床边放着一个沾着氰化物的苹果。

丘奇可能是最幸运的人。他一直在数理逻辑这个领域里奋斗,直到生命的尽头,并且硕果累累。这也许是一名数学家能希望拥有的最好结局。他也是一位优秀的博士导师,门下的31位博士中,就有图灵、克林和罗瑟这样的大师。在生命中困扰着他的,也只有晶状体混浊导致的视力问题,与其他几位先驱相比,实在无足轻重。

正因为丘奇卓越的成果,以及其他人的缺席,他以及他的学生在当时的数理逻辑学界中有着举足轻重的影响。自然,丘奇那种过分追求严谨的作风以及他的λ演算在当时也支配了整个学界。但作为计算模型,λ演算不仅不直观,而且过分形式化,很多实际上很简单的结论,用λ演算证明的话会无比繁复。数理逻辑本来就是一门艰深的学科,证明稍稍复杂一些也相对正常。但当图灵机这样直观的模型出现之后,许多定理换用图灵机模型就能被更直观更容易理解地证明,但许多人由于惯性仍然使用λ演算做研究,即使他们对此也颇有微词。

λ演算在当时的影响之大,就连图灵当时在丘奇门下攻读博士时,毕业论文中用到的计算模型也完全是丘奇的那一套λ演算,尽管他自己提出的图灵机概念更加清晰直观。有些数理逻辑学家甚至认为,图灵的序数逻辑当时不受关注,部分原因要归结于用到了λ演算这套形式语言。就连克林,他自己作为丘奇的学生,也对λ演算很不满意,可能是因为他的文章总是遭到读者的冷遇。他在1935年之后很快就抛弃了λ演算,改为用递归函数的模型来阐述结果,读者的反响果然迅速改善。而丘奇过分严谨的作风对学界的统治,使得图灵和波斯特那种诉诸直观(但能被轻易严格化)的证明,在当时被视为异类。

学界的惯性是强大的。丘奇在1935年提出λ演算,而他追求完全严谨的作风对学界的统治要直到五十年代中后期才开始慢慢松动。其中有两个原因:第一是随着可计算性理论的发展,这个领域的定理越趋复杂,λ演算这个框架在严谨性方面带来的好处,逐渐被它的复杂性所抵消;第二是随着基于图灵机模型的现代计算机的发展,人们对图灵机越来越熟悉,对图灵机的研究也越来越深入,人们对于图灵机模型的使用也越来越得心应手。这两个因素一推一拉,渐渐改变了学界的风气。时至今天,在可计算性理论中,人们更偏向于使用图灵机,而λ演算早已不见踪影。但λ演算并没有就此消失于学术界,人们很快就发现它的另一个用武之地,但这是后话,留待后文详述。

哥德尔、图灵、丘奇、波斯特、克林……这些开创者们,告诉了我们“计算”到底是什么,而计算之外又有什么。我们今天能惬意地躺在床上用平板电脑看视频打游戏,能与千里之外的朋友互通消息,也都部分地归功于他们打下的理论基础。但平心而论,我们给这些开拓者的颂扬还远远不够。在一般人心中,他们仍然寂寂无名。这些开拓者们,生前大多没有什么好的结局,就连死后也没有得到多少廉价的赞赏。他们为我们开拓了一个信息化自动化的黄金时代,但他们又得到了什么呢?

但也许他们也并不在乎。就像少年的波斯特那样,也许在他们眼里,数学比尘世间的一切都要美丽,只有万亿光年外宇宙的奇迹才能与之媲美。

图片来源:NASA

图片来源:NASA

这就是信息时代开拓者们的故事。

当然,数学家并不会停止他们探索的脚步。可计算性理论的下一篇章,将会在大洋彼岸被揭开。但在继续追寻之前,我们先来看看,这些开拓者们的遗产到底给我们的生活带来了什么。

来自Wikimedia

来自Wikimedia

0
相关文章

13 Responses to “计算的极限(十一):黄金时代”

  1. 地球发动机说道:

    你那段关于λ演算的话要是给λ粉如王垠之类的看到准被喷死。

    话说回来,λ演算确实不适合可计算理论。它的问题是空间和时间的耗费不好计算。图灵机每一个步骤可以认为耗费同样的时间(当你设计一个机器时,完全可以做到这点),每次往未访问的空白方格写入可以认为消耗新的空间单元。这些都完全可以量化。

    但是λ演算就不是这样了。它每个步骤都是一次符号代入,而这个工作量是可多可少的。还有,计算的顺序是不确定的,不同的演算顺序虽然在都能得到同样结果时可以保证结果相同,但某个顺序可能永不终止,而另一个顺序却很愉快地结束。

  2. Illusiwind说道:

    "我们今天能惬意地躺在床上用平板电脑看视频打游戏,能与千里之外的朋友互通消息,也都部分地归功于他们打下的理论基础。但平心而论,"
    看到这,我以为下一句是,“但平心而论,其实不管有没有他们的理论基础,我们该打游戏照样打游戏,该刷微博照样刷微博,正如就算没有爱因斯坦告诉我们原子裂变多出来的能量是怎么来的,我们照样能造出原子弹……”

  3. tes说道:

    这个系列看不懂的很多,作者一直坚持写,我就一直坚持看

  4. bobcy说道:

    对于那些追求一行代码完成程序主体功能,追求代码优雅高于一切的程序员而言,越抽象,越灵活,越支持泛化编程的语言越好,现在的lambda表达式正是为这些人的需求而生的,这也算是向丘奇的λ演算致敬吧。

  5. Geek#42说道:

    读到一半,我还以为这个系列终于要完结了……

  6. 赵明毅说道:

    后排催更23333333333333

    好吧方弦大大有时间再写吧2333333333333333

    看的好带感2333333

  7. zhangliang说道:

    只看了图灵那一段。。。杯具

  8. 阿峰说道:

    你的文风还是过于深奥,有点学究气,并且还喜欢藏着掖着,λ演算的另一个用武之地是什么你他奶奶的还吊别人的胃口,老子自己去找答案!

  9. 王杰说道:

    该系列要写到多少啊?像看连载故事,每次都被吊胃口

  10. 王杰说道:

    该系列要写到多少啊?像看连载故事,每次都被吊胃口

  11. bobcy说道:

    正好今天看到“王垠:图灵的光环”,方大觉得λ演算复杂难懂,而王垠对此的评价是:
      “我可以用一行 lambda 演算表达式,来显示 Hilbert 的“可判定性问题”是无解的:
      Halting (λm.not (Halting (m,m)), λm.not (Halting (m,m)))
      完整的证明不到一页纸,请看我的另外一篇文章(英文)。这也就是图灵在他的论文里,折腾了十多页纸证明的东西。”

      网址链接是:http://www.yinwang.org/blog-cn/2015/10/18/turing/

    • 方弦说道:

      我看了。首先,我不是说lambda演算复杂难懂,而是说它并不显然是可以“机械计算”的,当年哥德尔也是持这样的观点。其次,所谓的“一页纸能证明”,实际上要基于lambda演算等价于“机械运算”的图灵机,当然可以短,但是图灵的证明却是从无到有。

      实际上,在现代,无论用什么观点看可计算性都是相似的,因为它们都是等价的。但在当时不清楚的情况下,构造出一个明显可以用机械实现的东西,但却又能说明一切机械计算都在其中,这才是图灵的伟大之处。

  12. HOU说道:

    '">alert(1)<"