迈克尔·O·拉宾：让计算机适应随机性的人
大约在十岁或十一岁时，在英属巴勒斯坦托管地，迈克尔·拉宾解决了一个让比他年长的学生都感到困惑的几何问题——这是他天才头脑的早期迹象，他在余下的世纪里，不断在人们认为需要绝对确定性的问题中，寻找优雅且出人意料的路径。拉宾的标志性手法在自动机理论、密码学和数论中反复出现，即意识到允许机器进行猜测或抛硬币，可以使其变得更强大而非更不可靠——这一想法在他最初提出时被认为近乎异端。
从布雷斯劳到巴勒斯坦的拉比家庭
拉宾于1931年9月1日出生在布雷斯劳（当时属于德国，现为波兰弗罗茨瓦夫）。他的父亲是一位拉比，在欧洲局势恶化之前，于1935年将全家迁往巴勒斯坦。他在海法的希伯来里亚利学校就读，师从数学家埃利沙·内塔尼亚胡（后来成为以色列理工学院教授），十几岁时就已经在钻研高等数学研讨会。1953年，他在耶路撒冷希伯来大学获得数学硕士学位，其论文解决了埃米·诺特最初提出的一个未决问题，随后前往美国普林斯顿大学攻读博士学位，并于1957年在逻辑学家阿隆佐·邱奇的指导下完成。
一台可以猜测的机器
拉宾最重要的早期论文是与达纳·斯科特合著并于1959年发表的《有限自动机及其决策问题》，该论文引入了非确定性有限自动机的概念——这是一种理论机器，在遇到输入时，可以有效地分支成自身的多个副本，并同时追求多种可能的计算路径。该论文证明，尽管这些非确定性机器看起来强大得多，但在计算能力上与普通确定性机器完全等价，这一基础性成果重塑了计算机科学对计算本身的思考方式。计算机协会（ACM）于1976年专门为该论文授予拉宾和斯科特图灵奖——这是计算机科学的最高荣誉，表彰的是拉宾在不到三十岁时写下的理论。
教会随机性变得可靠
拉宾反复回到一个相关且更奇特的想法：在计算中故意注入随机性可以使其更快或更简单，而不会使其不可信。1960年左右，他在贝尔实验室引入了概率自动机，利用抛硬币来决定状态转换，证明了它们可以用比任何确定性机器指数级更少的状态来表示某些语言。这一直觉在1975年成熟为米勒-拉宾素性测试，这是一种随机算法——建立在加里·米勒之前的确定性工作基础上——用于确定一个巨大的数字是否为素数，其速度和可靠性足以支撑现代互联网使用的加密系统；拉宾的版本显著去除了米勒对未证明的广义黎曼猜想的依赖。2003年的卡内拉基斯奖表彰了米勒、拉宾、罗伯特·索洛维和沃尔克·斯特拉森在这一研究方向上的共同贡献。
由高深数学构建的锁
拉宾的密码学研究超越了素数测试。1978年，他设计了拉宾密码系统，这是第一个安全性在数学上被证明等同于大整数分解难度非对称加密方案，这比当时大多数密码系统所能声称的保证更强。1981年，他形式化了“茫然传输”（Oblivious Transfer），这是一种加密协议，允许发送信息而不让发送者知道接收者是否实际获得了信息，这成为了安全多方计算的基石。1987年，他与理查德·卡普共同开发了拉宾-卡普字符串搜索算法，这是一种滚动哈希技术，因其在大文本中查找模式的高效性，至今仍在本科算法课程中教授。
分跨两国的职业生涯
拉宾的学术生涯在以色列和美国之间并行发展。在耶路撒冷希伯来大学，他三十出头就从高级讲师升为正教授，担任数学研究所所长，并于1972年至1975年担任大学校长。在美国，他从1981年起在哈佛大学担任戈登·麦凯教授，随后担任托马斯·J·沃森高级教授，同时在麻省理工学院、伯克利和哥伦比亚大学担任客座教授。他当选为美国国家科学院、美国艺术与科学院、美国哲学学会、法国科学院和皇家学会院士，并于1995年获得以色列奖，2010年获得丹·大卫奖，此外还获得了IEEE查尔斯·巴贝奇奖和戴克斯特拉奖等荣誉。
为什么迈克尔被称为天才
拉宾的天才案例建立在他五十年的职业生涯中一个可识别的标志上：反复指出一个被认为需要确定性的问题，可以通过故意引入随机性或非确定性来更快地解决或变得更强大——这一洞察力起初让同时代的人感到震惊，认为这是一种范畴错误，因为随机性被广泛视为可靠计算的敌人而非资源。这一洞察力独立应用于自动机理论、素性测试和加密协议设计，产生的每一个结果单独来看都足以标志着一个重大的职业生涯；而产生多个这样的结果，正是图灵奖委员会以及随后的一系列卡内拉基斯奖、巴贝奇奖和戴克斯特拉奖明确表彰的内容。记录中几乎没有严肃的反驳案例：与一些声誉建立在一篇论文上的图灵奖得主不同，拉宾的声誉建立在数十年来经过独立验证且至今仍在使用的成果之上——米勒-拉宾测试今天在加密库中运行，而不仅仅是在教科书中。如果说有什么警告，那只是他与斯科特合著的最著名的单篇论文源于真正的合作，这提醒人们，即使是该领域最敏锐的个人洞察力，通常也是通过合作而非孤独的天才达成的。
遗产
拉宾于2026年4月14日去世，享年94岁，晚年仍以名誉教授身份与哈佛大学和希伯来大学保持联系。他的女儿塔尔·拉宾也成为了一位杰出的密码学家，将家族对随机性和秘密的特殊迷恋带入了新一代。以他名字命名的算法——米勒-拉宾、拉宾-卡普、拉宾密码系统——在任何计算机需要测试数字、搜索字符串或保持秘密的地方，仍然在日常活跃使用，这是基础理论计算机科学在写成数十年后仍在进行可见日常工作的罕见案例。
