1976 年，在牛津大学任数理逻辑教授的 Dana Stewart Scott 和在希伯来大学任教的 Michael O. Rabin 一同被授予图灵奖。他们在 1959 年合作的论文“Finite Automata and Their Decision Problems”（有限自动机与其判定性问题）提出了非确定自动机的概念，被证明是计算理论科学研究中的一个非常重要的概念，这篇经典论文后来成为这个领域后续研究的灵感源泉。
图注：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 而言，音乐在他的一生中占有极其重要的地位，他的妻子、女儿和孙女也都是专业级的古典音乐家。
值得一提的是，艾伦·图灵曾是二战前 Church 的博士生。当时，Church 很固执地让 Turing 在他关于超限计算的所有工作中都使用 lambda 演算。后来图灵曾对此抱怨，但为了获得博士学位，他不得不听从导师的要求。Scott 坦言，他觉得这两人其实关系一直不怎么亲近，而且，在他读研究生的时候，从来没听导师谈起过图灵。
不过，Church 对 Scott 的博士论文选题倒没有加以干涉。通常情况下， Church 会与学生们讨论各自感兴趣的研究领域，然后放手让他们去做。对于 Church 的放养式指导，Scott 很不客气地说，Church 主要是纠正了他论文中的拼写错误。在与 Tarski 发生过不愉快之后，他与 Church 之间的合作又变得不顺利了。
1958 年夏天，Scott 在普林斯顿大学的博士学位后，就到高级研究所（Institute for Advanced Study）里冯·诺依曼建造的计算机上做一些编程工作。当他来普林斯顿读博的时候，冯·诺依曼就已经躺在了医院里，所以一直没有机会见到他。冯·诺依曼去世后，他建造的那台计算机被转移到普林斯顿，Scott 解释，这是因为高级研究所一直都不想做工程方面的事情。
图注：现代计算机之父冯·诺伊曼
Scott 被聘请在这台计算机上做一个项目，他和一起合作的同事选择了五格骨牌（Pentominoes）的几何难题。受到 Dick 和 Emma Lehmer 在伯克利开发的回溯算法的启发，他们认为完全能够解决这个难题。
在普林斯顿的最后一个学年，Scott 曾遇到了从芝加哥大学来访的 Paul Halmos。两人在代数逻辑方面有着共同的兴趣，也是在 Halmos 的推动下，Scott 被邀请以非终身讲师的身份去到芝加哥，在那里担任讲师，直到 1960 年。
刚到芝加哥大学任教时，Scott 遇到了 Stanley Tennenbaum。他对 Scott 影响很大，两人一起做了很多工作。Tennenbaum 发现不存在满足一阶算术定律的可计算非标准模型，从而为 Emil Post 在递归函数理论中的问题提出了一个简洁的证明，在今天被称为“Tennenbaum 定理”。不过，由于一场盗窃，他们合作的大部分工作都未得以发表。Tennenbaum 的车被人闯入，那个装着他们所有文件的盒子被盗走，笔记全部丢失了。Scott 后来肯定地说：当小偷看到盒子里是什么时，这些笔记肯定在 10 分钟内就被丢弃了，所以它们从未得见天日。
比利时的数值分析师 René De Vogelaere 当时也在伯克利。他非常热衷于宣传使用 ALGOL 进行编程。在伯克利，Scott 还结识了许多来访问的逻辑学家。斯坦福大学的 John Myhill 和他合作了一篇关于“序数可定义性”（Ordinal Definability）的论文，表明可遗传的序数可定义集合形成了满足选择公理的集合论模型。哥德尔看到这项工作后说：「哦，我几年前就想到了。但我对可构造集合的证明要重要得多，我从来没有告诉过任何人。」 Scott 对此感到有些无奈：「好吧，就这样了」。
6 在斯坦福研究布尔值模型
1963 年，John Myhill 离开了斯坦福，所以斯坦福也就空出了一个职位。而此时的 Scott 在伯克利正经历着许多不愉快。伯克利的数学系正在大力引进教师、扩展规模，并且开始对 Tarski 有一定程度的敌意，因为他正大力推动逻辑学的发展。Scott 决定摆脱这种环境。
暑假期间，Scott 经常去斯坦福与 Patrick Suppes 一起工作。50 年代 Scott 在伯克利读本科时，就修读过他的课程，后来两人成了亲密的朋友。Suppes 一直对如何将逻辑应用于数学心理学感兴趣，两人在 1958 年合作写了一篇将测量理论与概率论联系起来的论文，Scott 在其中的贡献主要是在模型理论方面。
在 60 年代初期，斯坦福大学的 Georg Kreisel 教授开始定期访问斯坦福，正是他说服了 Scott 从伯克利搬到斯坦福。
在斯坦福，像 Georg Kreisel 这样的数学家开始倡导计算机科学在学科上应该更独立一些。以经典应用数学为主的数学系很乐意放弃数值分析的传统，来帮助组建新系。当时，Don Knuth 离开加州理工学院，加入斯坦福。麻省理工学院的 John McCarthy 也来斯坦福创办了他的人工智能实验室。Scott 倒没有直接参与计算机科学系的筹建，但他认识在那里的每个成员。
从芝加哥大学来到斯坦福的 Paul Cohen 发明了“forcing”，仅仅在少量信息的基础上就成功赋予了函数一些性质。而且，他不仅可以将其扩展到整数上的函数，还可以扩展到超有限域，并且他还用它来证明了连续统假设（Continuum Hypothesis）((f)) 独立于集合论公理。当时，所有人都被他的工作惊呆了。伯克利的 Robert Solovay 经常访问斯坦福，为的是能与 Cohen 交流研究，他们观察到，“forcing” 的概念可以为关于集合论的陈述赋予布尔值。
在 1966 年的新年假期中，Scott 对自己说：「等等。我为什么不首先从一个合适的布尔代数开始，然后用它来解释集合论，并以不同的方式来证明连续统假设的独立性？」最终，这个想法在论文中得以呈现，并获得了 1972 年 Leroy P. Steele 奖。
7 编程语言理论研究
Scott 在 1970 年代与编程语言设计先驱 Christopher Strachey 的合作奠定了现代编程语言语义学方法的基础。与 Strachey 的相识是在阿姆斯特丹大学。
图注：Christopher Strachey
从 1968 年开始，Scott 在阿姆斯特丹大学休了两年学术假。期间，他还认识了 Aad van Wijngaarden，他是 ALGOL 语言的设计者之一 。
IP卡
狗仔卡
发表于 2022-8-24 10:31
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡