1976 年,在牛津大学任数理逻辑教授的 Dana Stewart Scott 和在希伯来大学任教的 Michael O. Rabin 一同被授予图灵奖。他们在 1959 年合作的论文“Finite Automata and Their Decision Problems”(有限自动机与其判定性问题)提出了非确定自动机的概念,被证明是计算理论科学研究中的一个非常重要的概念,这篇经典论文后来成为这个领域后续研究的灵感源泉。
非确定性有限状态自动机开创者 Dana Scott:我获得图灵奖 ...-2.jpg(34.48 KB, 下载次数: 1)
图注:Dana Scott
作为一位在上世纪早期获得图灵奖的科学家,Dana Scott 是个典型的通才式科学家,他的研究涉及计算机科学家、数学和哲学等多个领域,他在自动机理论、模态逻辑、模型论、集合论和编程语言理论等问题上做出了开创性的贡献,尤其是域理论(domAIn theory),它分析计算机编程语言所必不可少的一种数学理论。
如今的 Dana Stewart Scott 已经 89 岁,从 CMU 退休后一直居住在加州伯克利。本文讲述了他在获得图灵奖之前 26 年求学、科研与教学生涯。在加州伯克利分校、普林斯顿大学、芝加哥大学、斯坦福大学、牛津大学等地,Scott 先后结识了一批伟大的数学家、计算机理论学家,并受到了他们的深刻影响。他曾师从逻辑学家 Alfred Tarski 和图灵的导师 Alonzo Church,Rabin 是他的师兄。70 年代,他遇到编程语言设计先驱 Christopher Strachey,与他的合作奠定了现代编程语言语义学方法的基础。
1
起于音乐的数学之旅
Scott 于 1932 年出生于加利福尼亚州伯克利,一家人住在苏珊维尔附近的一个农场,后来搬到了斯托克顿市。如今的他还记得,1941 年 12 月 7 日那天,街上的卖报声不绝于耳:「号外!号外!快来看啊:珍珠港被轰炸了」。
学生时期,Scott 对音乐产生了极大的兴趣,他学会了演奏单簧管,还上过一些钢琴课。在学习乐器的过程中,他开始思考乐器是如何发出声音的。他从乐队老师那里得到一本书“Science of Musical Sounds”(《音乐的声音科学》),他被这本书吸引住了。书中的数学知识又激发了他对数学的兴趣,叔叔给了他一本微积分的书,他便埋头啃了起来。
Scott 经常光顾周围总是尘土飞扬的州立图书馆。他在那里发现了 Helmholtz 关于声学和音乐理论的书,受其启发,他在高中慢慢地研究起了对数和傅里叶级数。高年级的时候,他做了一个关于声学的小项目,最终获得了西屋奖学金。
对 Scott 而言,音乐在他的一生中占有极其重要的地位,他的妻子、女儿和孙女也都是专业级的古典音乐家。
而在学习数学的路上,Scott 从高中数学老师那里得到了非常多的鼓励,所以高中时的他就下定决心,如果有机会上大学,一定要主修数学。Scott 的父母都没有上过大学,而他很幸运地获得了一笔小额奖学金,足够他进入加州大学伯克利分校学习。在他的所有直系亲属中,他是第二个获得大学学位的人。
2
伯克利:研究数理逻辑的起点
1950 年进入伯克利后,Scott 报名参加了逻辑入门课程,任课教师是哲学系主任 Paul Marhenke 教授。这门课对 Scott 来说不算难,他也开始喜欢上了逻辑学。升入大二后,Scott 修了更多哲学系 Benson Mates 教授的课,两人成了关系很好的朋友。Benson Mates 推荐他读 Alfred Tarski 的作品,Tarski 是全球逻辑学的领导者,此前他在波兰逃脱了犹太人的迫害,后来进入伯克利做数学教授。
非确定性有限状态自动机开创者 Dana Scott:我获得图灵奖 ...-3.jpg(30.58 KB, 下载次数: 0)
图注:Alonzo Church
值得一提的是,艾伦·图灵曾是二战前 Church 的博士生。当时,Church 很固执地让 Turing 在他关于超限计算的所有工作中都使用 lambda 演算。后来图灵曾对此抱怨,但为了获得博士学位,他不得不听从导师的要求。Scott 坦言,他觉得这两人其实关系一直不怎么亲近,而且,在他读研究生的时候,从来没听导师谈起过图灵。
不过,Church 对 Scott 的博士论文选题倒没有加以干涉。通常情况下, Church 会与学生们讨论各自感兴趣的研究领域,然后放手让他们去做。对于 Church 的放养式指导,Scott 很不客气地说,Church 主要是纠正了他论文中的拼写错误。在与 Tarski 发生过不愉快之后,他与 Church 之间的合作又变得不顺利了。
1958 年夏天,Scott 在普林斯顿大学的博士学位后,就到高级研究所(Institute for Advanced Study)里冯·诺依曼建造的计算机上做一些编程工作。当他来普林斯顿读博的时候,冯·诺依曼就已经躺在了医院里,所以一直没有机会见到他。冯·诺依曼去世后,他建造的那台计算机被转移到普林斯顿,Scott 解释,这是因为高级研究所一直都不想做工程方面的事情。
非确定性有限状态自动机开创者 Dana Scott:我获得图灵奖 ...-5.jpg(182.7 KB, 下载次数: 0)
图注:现代计算机之父冯·诺伊曼
Scott 被聘请在这台计算机上做一个项目,他和一起合作的同事选择了五格骨牌(Pentominoes)的几何难题。受到 Dick 和 Emma Lehmer 在伯克利开发的回溯算法的启发,他们认为完全能够解决这个难题。
然而,学校很快发现,让这台机器运转起来,实在太昂贵了。静电管受湿度的影响很大,而普林斯顿是个湿度很高的地方,所以,在冯·诺依曼机器上工作的最佳时间是凌晨 3 点。最后到了秋季的时候,学校再也不愿让他们继续了,于是关闭了计算机。
回顾在普林斯顿的时光,Scott 既十分怀念又感到些许的遗憾:“普林斯顿是一个非常令人兴奋的地方,因为有很多数学家到那里工作或访问,师资力量非常强大,但回想起来,如果我那时候能更多地利用我在普林斯顿学到的东西就好了。”
4
与 Michael Rabin 的合作
与 Scott 一起获得图灵奖的 Michael Rabin,当时是 Church 的另一位博士生,两人读博期间成了非常要好的朋友。1957 年,他们被选中在 IBM 约克镇高地研究中心进行暑期实习,一起研究有限状态自动机问题。
非确定性有限状态自动机开创者 Dana Scott:我获得图灵奖 ...-6.jpg(51.13 KB, 下载次数: 0)