上一期讲了，第10届图灵奖得主，是奖励给两个人，那是一对师生。这一次，图灵奖评选委员会又奖励给了两个人。从技术上来讲，没有这两个人的工作，像加密货币，区块链这些东西，在安全性上，可能都有很大的欠缺。这两个人是同门师兄弟，当时在以色列希伯莱大学任教的米凯尔.拉宾（Michael O. Rabin）和在英国牛津大学任数理逻辑教授的达纳.斯科特（Dana Steward Scott）共同获得。拉宾和斯科特是师兄弟，两人在20世纪50年代中期先后师从著名的逻辑学家和计算机专家阿隆索.邱奇（Alonzo Church）。
必须要讲先讲一下这个老师，阿隆索.邱奇是何方神圣？对计算机不了解的人可能会觉得，这家伙这么牛逼，为什么不能获得图灵奖呢？这样说也没错，就算他的成就再大，也不可能给他发一个图灵奖，因为图灵也是他的学生。图灵搞的图灵机，不能说跟他老师搞的一模一样吧，只能说把他老师搞的lamda运算发扬光大了。
当我们说一个老师很牛逼的时候，一般会说这个老师桃李满天下。一般来说，这句话是又假又大又空的话。哪有这么多桃李满天下，不出几个危害社会的人渣就不错了。但是这句话放在邱奇的身上，就非常的贴切。他亲自带出来的博士生有31名，这31名学生，个顶个的有自己的Wikipedia，不是教授就是科学家，还是那种不可忽视的科学家。他的学生再教其它学生，就把邱奇的影响力放的越来越大。像雷蒙德·斯穆利安这种谁也不服的人，说起他的老师，那也是一毕恭毕敬。这个家伙是一个精通数学，计算机，魔法和中国道家的复合型人才，我放一张照片看看，仙风道骨的样子。
但是他没有获得图灵奖，他的故事比图灵奖得主的故事可要有趣多了。他是被人拍纪录片的人。《This Film Needs No Title: A Portrait of Raymond Smullyan.》这部电影不需要标题。这个以后有机会讲讲他也不错。
还是说回来，这两个人，为什么能获得图灵奖呢？他们共同发明了λ-演算，并提出“任何计算，如果存在有效过程，它就能被图灵机实现”的命题（即“邱奇论题”）而闻名于世。他们还在有限自动机及其判定问题的研究中合作，奠定了非确定性有限状态自动机的理论基础。之后，两人的研究方向有所不同：拉宾侧重于计算理论，而斯科特则专注于逻辑学在计算机科学中的应用。他们各自在各自的领域中取得了重大成果，做出了创造性的贡献。
拉宾于1931年9月1日出生在德国的布雷斯劳（Breslau，二战后成为波兰的弗罗茨瓦夫）。他的父亲是一位犹太教教士和博士，在当时著名的布雷斯劳神学院教授犹太历史和哲学，还曾担任院长。拉宾的母亲也是一位知识分子，拥有文学博士学位，年轻时就开始创作儿童文学。纳粹上台后，拉宾的父亲因为曾在俄罗斯生活过，凭借政治敏感性，预感到即将发生动荡和麻烦，建议神学院迁往耶路撒冷，但未获同意。于是，全家于1935年迁往巴勒斯坦，躲过了一劫。1948年以色列建国后，他们成为以色列公民。
拉宾在地中海边的港口城市海法度过了他的童年和少年时代。读了著名微生物学家保罗·德克吕夫的《微型猎人》后，他幻想自己将来成为一名微生物学家。有一次，他和高年级的学生比试解欧几里德几何题，竟然赢了，这让他对数学产生了兴趣。因此，从莱利学院毕业后，他进入希伯来大学学习数学。在那里，他读到数学家克林的《元数学》一书，第一次接触到图灵关于可计算性的概念和图灵机这一理论模型，立刻被深深吸引。但为了打好数学基础，他的硕士论文选择了抽象代数中一个关于可交换环理论的问题，这是当时由德国女数学家埃米·诺特创立的领域。获得数学硕士学位后，拉宾去了美国。20世纪50年代初，以色列刚建国，经济和科技都还不够发达，研究计算问题的人很少，甚至连计算机都没有。
拉宾到美国后，先在宾夕法尼亚大学攻读博士学位。他的博士论文将他熟悉的抽象代数和他感兴趣的可计算性问题结合在一起，研究群的可计算性问题。拉宾在论文中证明了与群相关的许多问题，例如群是否符合交换律，都是无法由计算机解决的。
让拉宾成名的并不是他的博士论文，而是源于1957年在IBM研究中心的一个暑期工作机会。当时，IBM允许他和师弟斯科特从事他们感兴趣的任何研究。于是，拉宾和斯科特联手研究了图灵提出的计算模型，也就是图灵机。
图灵机是一种不能往磁带上写的计算机，被称为有限状态自动机（finite state automata，缩写FSA）。图灵在研究这种机器时的基本信条是：机器在相同输入情况下，其“心智状态”也相同，也就是说，对于具有给定指令集的机器而言，一定输入的机器总是以同样的方式运行。拉宾和斯科特认为，这种“确定性”行为的机器存在局限性。因此，他们定义了一种新的“非确定性”的有限状态自动机（nondeterministic finite state automata，缩写NDFSA）。这种机器在读取到某个输入后，有一个可能的新状态的“菜单”供选择，从而使得对给定输入的计算结果不再单一，每个选择代表一种可能的计算。
拉宾和斯科特将图灵的有限状态自动机从确定性扩展到非确定性，极大地推动了有限状态自动机理论的发展。尽管非确定性有限状态自动机的能力并不比确定性的更强（拉宾和斯科特自己证明了任何可以用非确定性机器解决的问题都可以在确定性机器上解决，并提出了将非确定性机器转换为确定性机器的方法），但它可以简化机器描述并加快解题速度。后来的实践证明，非确定性有限状态自动机在机器翻译、文献检索和字处理程序等应用中发挥了重要作用。
拉宾和斯科特的研究成果在两年后发表于IBM公司的研究和开发杂志上，论文题为《有限自动机及其判定问题》（Finite Automata and Their Decision Problems）。
1958年夏天，拉宾再次来到IBM。当时，“人工智能之父”约翰·麦卡锡（J. McCarthy，1971年图灵奖获得者）正在研究如何在巴克斯（J. Backus，1977年图灵奖获得者，下一期就讲他了，请大家不要换台）发明不久的Fortran语言中加入表处理功能。
在这里，麦卡锡和拉宾发现，他们是校友，而且还是同一个系的，而且，他们的数学老师都是丘奇。虽然麦卡锡的博士生导师是唐纳德·斯宾塞。但是他的老板，也就是达特茅斯学院的校长凯梅尼，同时也是BASIC语言的发明人，是丘奇的学生，总之，没有外人。
在这里，麦卡锡给校友出了个难题：设计一种即使口令被敌方窃取也无法进入系统的方案。经过艰苦探索，拉宾利用冯·诺伊曼开发的一个单向函数解决了这个问题。所谓单向函数是一种特殊的数学函数，具有以下两个关键特性：
- 容易计算：对于给定的输入 x，计算函数值 f(x) 相对容易且快速。
- 反向计算困难：已知 f(x) 的情况下，推导出原始输入 x 非常困难，甚至在计算上不可行。
通俗地说，单向函数的正向计算（从 xx到 f(x)）很容易，但逆向计算（从 f(x) 回到 x）几乎是不可能的。这个性质使得单向函数在密码学中非常重要，特别是在设计安全的密码系统、数字签名和认证协议时。
我举个例子，比如，现在基于哈希的就是单向函数，比如MD5，SHA-256都是这一类，在现在的Bitcoin中，使用SHA-256作为其挖矿算法和交易签名的哈希函数，确保交易的完整性和不可篡改性。还有一类是基于乘积的单向函数，比如基于大数的因数分解问题，例如RSA算法，利用公钥加密、私钥解密的机制，广泛用于安全通信和数据保护。还有一类是椭圆曲线密码学 (ECC)，ECC基于椭圆曲线离散对数问题，提供更高的安全性和效率。比如ECC加密：具有相对较小的密钥长度，但提供与传统加密算法（如RSA）相同的安全性。还有ECDSA（椭圆曲线数字签名算法）：用于数字签名，广泛用于SSL/TLS协议和加密货币（如比特币）。
研究这个的先驱就是拉宾，这个要感谢校友麦卡锡，正是他，促使拉宾进一步研究计算任务的最小计算量这一一般性问题，也就是计算的固有难度问题，从而成为最早研究计算复杂性问题的先驱之一。
1959年和1960年，拉宾在耶路撒冷发表了两篇关于此问题的论文，即《计算速度和递归集合的分类》（Speed of computation and classification of recursive sets, 3rd Convention of recursive sets, Tech. Rep. No.1, O. N. R., Jerusalem, 1960）。虽然论文中没有使用“计算复杂性”这个名词，而是用了“计算速度”和“计算难度”等词汇，但学术界公认这两篇论文是研究计算复杂性的最早、最权威的论文之一，对1964年正式提出“计算复杂性”这一术语的哈特马尼斯（J. Hartmanis）和斯特恩斯（R. E. Stearns，这两人是1993年图灵奖获得者）以及计算复杂性理论的另一奠基人布卢姆（M. Blum，1995年图灵奖获得者）都产生了深刻影响。其中，布卢姆正是听了拉宾的演讲后才开始研究计算复杂性，并完成了他的博士论文。
拉宾的研究成果在一定程度上改变了人们的研究方向。例如，波兰数学家普里斯伯格（M. Presburger）在1930年于华沙举行的国际数学家会议上提出了一个命题：只包括自然数相加运算的数学系统是完备的，也就是说，这样的系统在图灵机上都是可计算的。因此，这被称为普里斯伯算术系统。许多计算机科学家试图编写出能证明这个系统中的定理的计算机程序。
然而，拉宾指出，这种尝试极其困难，几乎无法实现。对于一个只有100个符号的系统，即使有1万亿台每秒运行1万亿次的计算机，也要运行1万亿年才能得出结果！1974年在斯德哥尔摩的IFIP大会上，拉宾和耶鲁大学的费歇尔（M. Fisher）公布了他们的研究成果，宣称“这是通向人工智能的理论障碍”。巧合的是，拉宾演讲那天，正值美国总统尼克松因水门事件宣布辞职。拉宾原以为代表们会去看尼克松演讲的电视转播而不会有多少人来听他的演讲，但出乎意料的是，一开始人们就像潮水一样涌进会场，对演讲反应十分热烈。拉宾讲完后，人们在麦克风前排起长队提问。
对于那些从事普里斯伯格系统研究的人来说，听了拉宾的演讲后感觉非常失落，似乎“世界末日”到了。但拉宾本人并不悲观。他认为应该放弃的是以完全确定的方式获得结果，因为这种方式可能出错，尽管出错的可能性微乎其微。拉宾建议使用概率算法（probabilistic algorithm，或称随机算法，randomized algorithm）来解决这类问题，这也是他的一个重要贡献。
所谓概率算法，是指带有随机操作的一类算法。这种算法在计算的某一步或某些步产生符合规定要求的随机数，然后根据产生的随机数决定下一步的计算。例如，在某一步有两种选择：执行A或执行B，此时随机产生一个0或1，若产生的是0则执行A，若产生的是1则执行B。这相当于根据掷一枚硬币的结果（正面或反面）决定下一步的计算。
概率算法的思想最早用于数值计算，通常称作蒙特卡罗法。这一方法在20世纪40年代提出，其基本思想是建立概率模型，通过统计模拟或抽样得到问题的近似解。通常要求计算结果的期望值等于问题的精确解，并且计算误差的期望值随可供使用的时间增加而减小。
蒙特卡罗法是一种基于概率统计的计算方法，用于解决复杂问题或评估数学问题的方法之一。它的基本思想是通过随机抽样和统计模拟来获得问题的近似解，而不是通过解析求解。蒙特卡罗法通常适用于那些难以通过传统方法求解的问题，尤其是涉及大量随机因素或复杂概率分布的问题。
在过去的20年里，概率算法在非数值计算中得到了广泛应用。例如，已经设计出关于排序和搜索、素数判定、有限域上的多项式分解和求根、字符串模式匹配等方面的有效概率算法。概率算法同样也应用于并行计算，发展出了概率并行算法。甚至，除了经济、科学这些领域已经在大规模使用蒙特卡罗法。这些年我看到已经有人使用这个算法搞玄学计算了，期待早日出成果，算一算我的桃花运什么时候到来。
利用这种概率算法的思想，拉宾在1974年斯德哥尔摩的演讲中首次萌发了这一想法，但当时这个概念还不够成熟。第二年休假时，他前往麻省理工学院，了解了加里·米勒（Gary Miller）的研究成果。米勒证明了利用著名的黎曼假设，可以用一般的确定性算法来判断很大的数是否是素数。拉宾结合了米勒的研究结果和数论中关于素数密度的理论，在1976年提出了一个判定素数的概率算法，取得了巨大成功。
这个算法的理论根据是：当n是合数时，在1到n-1的整数中有一半以上会是n为合数的“见证人”。算法的基本做法是：随机地产生一个介于1与n-1之间的整数b，检查b是否是n为合数的“见证人”。若b是“见证人”，则计算结束并得出n为合数的结论；否则重复这个过程。至多进行k次，若产生的k个随机数b都不是n为合数的“见证人”，则得出n为素数的结论。算法所需的时间为O（log3n）。
当计算的结果是n为合数时，结果肯定是正确的。但是，“n为素数”的结果有可能是错误的。此时n为合数的概率，即得出错误结论的概率不超过1/2k。当k足够大时，这个概率会很小。例如，取k=10，错误的概率小于0.001。这已经是在实验中几乎不可能发生的事件了。实践证明，该算法在实际使用中几乎不会给出错误的结论。
拉宾的同事普拉特（V. R. Pratt）利用拉宾提出的算法编写了一个程序，在1975年冬找到了当时已知的最大素数2400-593，以及最大的孪生素数k×338+821和k×338+823（其中k是小于300的所有素数的乘积），创造了世界记录。拉宾的算法至今仍然是寻找素数的最快算法之一。
概率算法在分布式计算、通信、信息检索、计算机安全等领域都有广泛应用。目前，连接高度并行计算机的专用网络上发送信息的算法是由拉宾的另一位同事瓦里安特（L. Valiant）设计的一种随机算法。该算法不直接将信息发送到目的地，而是先发送到任意一个节点，然后由该节点再将信息发往目的地。瓦里安特证明了这种看似疯狂的方法能有效地减少网络中的竞争，避免阻塞。这展示了随机化在解决复杂问题中的威力和魅力。
在密码学领域，目前广泛采用的公开密钥体制（public key）和RSA算法（Rivest-Shamir-Adleman algorithm）也运用了拉宾的随机化和概率技术。然而，正如许多技术一样，好的技术也可能被用来进行恶意行为。1988年11月，在互联网上广泛传播的蠕虫病毒正是拉宾在哈佛大学时的一个学生罗伯特·莫里斯（Robert Tappan Morris）利用学到的随机化技术设计并传播的。
蠕虫病毒本身是无害的，并且在一段时间内不会被注意到，它有一个关键的缺陷，导致了更广泛的问题。蠕虫病毒会不加选择地从一个系统传播到另一个系统，因此莫里斯添加了功能，这样它就可以检查它试图感染的系统以前是否受到感染。如果它确定系统已经被感染，它就不再感染。这个特性可以被用来对抗蠕虫病毒以阻止它的蔓延，因为感染过了就不再感染了，相当于打疫苗了。当时莫里斯学到了随机化技术，就写了一段代码，给病毒增加了一个随机化因子，随机在已经感染过病毒的七台机器中，找一台倒霉蛋来搞个二阳。谁曾想，他写的随机化有问题，最后导致每台机器都何止二阳，全都是运行数十份病毒，都感染了好几十遍，把系统给整死机了。
再来说说斯科特，他比拉宾小一岁，生于1932年10月11日的加利福尼亚州。在加州大学伯克利分校获得学士学位后，他前往普林斯顿大学研究生院深造，师从阿隆索·邱奇，与为师兄弟。邱奇对学生要求十分严格，布置的问题也颇具挑战性，因此斯科特一开始难以适应，常感精神紧张，甚至经常在夜里做恶梦。但他通过不懈努力，最终能够从容应对。
1957年暑假，他与师兄拉宾合作完成了对图灵机的研究，并提出了非确定性有限状态自动机的理论。随后，他于1958年取得博士学位。之后，斯科特在芝加哥大学、加州大学伯克利分校、斯坦福大学、荷兰的阿姆斯特丹大学、普林斯顿大学以及英国牛津大学等国际知名高等学府任教。1981年，他受聘于卡内基-梅隆大学，担任计算机科学、数理逻辑和哲学教授。
斯科特的主要兴趣和研究方向是逻辑学，涵盖了广泛的领域，包括集合论、模型论、自动机理论、非经典逻辑中的模态逻辑和直觉主义逻辑。直觉主义逻辑是为了解决数学研究中的悖论而提出的，认为数学处于首要地位，逻辑则是数学思维的抽象。斯科特在这些领域都作出了不同程度的贡献。
然而，斯科特最大的贡献在于与斯特雷奇合作，在20世纪60年代提出了程序设计语言的“标志语义模型”，为标志语义学奠定了坚实的基础。在此之前，霍尔已经建立了公理语义学作为一种形式化程序设计语言语义的方法，但公理语义学是不完备的。标志语义学将语言中的每个成分与一个数学对象相对应，称为从前者到后者的映射，后者称为前者的“标志”。这个数学对象形成一个格，其中的偏序关系由“定义范围小于等于”确定。标志语义学被广泛应用于定义大型程序设计语言、数据库和操作系统等。IBM的维也纳实验室开发了META IV元语言，成为描述大型软件的强大工具。随后，它发展为维也纳开发方法VDM，成为程序开发的通用形式化方式。ISO正在制定与VDM相关的规约语言VDM-SL。
在建立标志语义学的过程中，斯科特还创建了域论，旨在回答语义域方程是否存在数学对象作为其解，以及是否存在有效的方法来定义这些数学对象上的可计算函数，包括描述程序设计语言所需的函数。虽然域论起初是作为斯科特研究标志语义学的“副产品”，但由于其重要性，已经成为一门独立的数学分支学科，受到广泛重视。在一些文献资料中，标志语义学被翻译为“指称语义学”。
在获得图灵奖之前，拉宾曾于1974年获得由罗斯柴尔德基金会颁发的数学奖，而斯科特则于1972年因在数理逻辑方面的出色贡献而获得美国数学会的Leroy P. Steele奖。1980年，拉宾又被授予哈维科技奖。至于其它的奖，就不再多说了，反正很多。
拉宾和斯科特是在1976年10月20日于休斯敦举行的ACM年会上被授予图灵奖的。两人分别发表了图灵奖演说，拉宾的演说题为“计算复杂性”，而斯科特的演说题为“逻辑与程序设计语言”。这些演说刊载于《ACM通信》（Communications of ACM）的1977年9月期。
这两个人目前还建在，一个今年91岁，一个今年92岁，一个是1931年出生的，一个是1932年出生的，希望两位老人长命超过一百岁。
博客没见到仙风道骨的图啊 栋哥