一个反直觉的事实：计算机科学最基础的理论突破，往往来自对"随机性"的重新理解。迈克尔·拉宾（Michael Rabin）——这位刚于2026年4月14日去世的图灵奖得主——一生都在证明：让计算机掷硬币，有时比让它按部就班计算更高效、更安全。
94岁的拉宾留下了什么？不只是1976年与达纳·斯科特（Dana Scott）共享的图灵奖，更是一整套改变数字世界的思维工具：从密码学到分布式系统，从算法设计到零知识证明，他的 fingerprints 遍布现代计算的底层架构。
正方：随机性是计算的本质升级
拉宾的核心洞见可以概括为一个简单问题：如果允许计算机在计算过程中"掷硬币"，它能解决什么确定性算法解决不了的问题？
1959年，拉宾在IBM的Lamb Estate度过了一个改变命运的夏天。他与斯科特合作的论文《有限自动机及其判定问题》，首次系统性地引入了非确定性自动机（nondeterministic automata）的概念。这不是什么工程优化，而是对"计算"本身的重新定义——机器不再被束缚于单一路径，而是可以同时探索多种可能性。
这一理论框架直接催生了计算复杂性理论的核心分类：P类问题（确定性多项式时间可解）与NP类问题（非确定性多项式时间可解）。今天每个计算机科学学生都要背诵的P vs NP问题，其思想源头正是拉宾与斯科特的那篇论文。
但拉宾没有停留在理论。1976年，他与理查德·卡普（Richard Karp）合作，将随机性引入素数测试——米勒-拉宾素性测试（Miller-Rabin primality test）。这个算法的革命性在于：它用随机采样替代了穷举验证，将素数判定的时间复杂度从指数级降到了多项式级。
更关键的是，它为现代密码学奠定了数学基础。RSA加密、椭圆曲线密码学，都依赖于快速生成大素数的能力。没有拉宾的随机化算法，今天的HTTPS连接可能要慢上几个数量级。
拉宾的另一项开创性工作是不经意传输（Oblivious Transfer, OT）。1981年，他提出了一种协议：发送方传递两条信息，接收方只能获取其中一条，而发送方无法知道接收方选择了哪一条。这个看似简单的设计，成为安全多方计算的基石——从隐私保护机器学习到区块链混币协议，OT 无处不在。
用拉宾自己的话说：「数学家当时完全不认可这些关于计算的研究，他们没意识到一个新领域正在诞生。」（"There was absolutely no appreciation of the work on the issues of computing. Mathematicians did not recognize the emerging new field."）
反方：随机性只是权宜之计，确定性终将胜利
对拉宾的随机化范式，学术界从未停止质疑。批评者的核心论点有三：
第一，随机性是"偷懒"的证明。2002年，印度数学家马宁德拉·阿格拉瓦尔（Manindra Agrawal）与同事证明了AKS素性测试——一个完全确定性的多项式时间素数判定算法。这意味着拉宾的米勒-拉宾测试虽然实用，但并非理论上不可替代。随机性带来的效率优势，可能只是因为我们还没找到聪明的确定性方法。
第二，随机性的安全性是概率性的。米勒-拉宾测试有极小的概率将合数误判为素数（尽管可以通过重复测试将错误率压到可忽略）。在密码学场景中，这种"几乎肯定"是否足够？批评者认为，真正的安全应该建立在数学必然性之上，而非统计置信度。
第三，物理随机源的不可靠性。拉宾的理论假设计算机能获取"真随机数"，但现实中的随机数生成器要么依赖物理噪声（难以验证其随机性），要么依赖伪随机算法（确定性程序的输出）。如果随机性本身可以被预测或操控，整个理论大厦的地基就松动了。
更激进的批评来自量子计算阵营。量子计算机的叠加态（superposition）看似实现了"真正的并行性"，但测量时的坍缩又引入了概率性。这究竟是随机性的终极胜利，还是证明随机性只是我们对量子力学不完备理解的副产品？
我的判断：随机性是一种认知工具，而非物理实在
拉宾的真正遗产，不在于证明了"随机性比确定性更好"，而在于展示了认知视角转换的价值。非确定性自动机、概率算法、零知识证明——这些工具的共同点是：它们改变了我们描述和思考问题的方式。
以零知识证明为例。拉宾与查理斯·拉科夫（Charles Rackoff）在1980年代参与发展了这一概念：证明者可以向验证者证明某个陈述为真，而不透露任何额外信息。这听起来像魔术，但其数学基础正是概率性交互——验证者通过随机挑战来确认证明者的诚实性，而非检查完整的计算轨迹。
今天，零知识证明正在重塑区块链行业。以太坊的扩容方案zk-Rollups、隐私币Zcash、身份验证协议，都依赖于这一技术。拉宾三十年前的理论探索，正在转化为降低交易费用、保护用户隐私的实际产品。
另一个被低估的贡献是拜占庭容错（Byzantine Fault Tolerance）的早期工作。拉宾研究的分布式系统共识问题，为后来的实用拜占庭容错（PBFT）算法、乃至比特币的工作量证明机制，提供了理论参照系。当 Vitalik Buterin 设计以太坊2.0的共识层时，他站在的正是拉宾等先驱搭建的概念脚手架之上。
拉宾的生平本身也构成一种隐喻。1931年生于德国布雷斯劳（今波兰弗罗茨瓦夫），1935年随家人移民巴勒斯坦，1948年因以色列独立战争中断学业——数学家亚伯拉罕·弗兰克尔（Abraham Fraenkel）向军方求情，才使他得以进入耶路撒冷希伯来大学。这种在动荡中寻找确定性的经历，或许塑造了他对"概率性安全"的直觉：没有绝对的安全，但可以通过设计将风险控制在可接受范围内。
29岁担任希伯来大学数学研究所所长，33岁成为正教授，却在1981年转投哈佛大学——不是因为耶路撒冷的学术地位不够高，而是因为「计算机科学」作为一个独立学科，在美国获得了更制度化的承认。拉宾的个人轨迹，折射出计算理论从数学边缘走向学科中心的历程。
值得玩味的是拉宾与约翰·麦卡锡（John McCarthy）的互动。1950年代末，正是麦卡锡在Lamb Estate向拉宾提出了那个关于"间谍、卫兵和密码"的谜题，催生了计算复杂性理论的早期论文。麦卡锡后来因发明"Lisp语言和人工智能概念"获得图灵奖，而拉宾则因"有限自动机"获奖——两个从同一场夏日讨论中生长出来的研究方向，最终汇聚成现代计算机科学的两大支柱。
拉宾晚年仍在活跃。他的最后几篇论文涉及量子计算中的随机游走和密码学的信息论界限。对于一个九十多岁的学者，这种持续产出本身就挑战了"创造力随年龄衰退"的常识。或许，随机化思维的优势之一就是：它不要求你找到唯一正确的路径，而是允许你在概率空间中持续探索。
为什么这件事现在重要
拉宾的去世恰逢一个关键节点：人工智能正在消耗全球算力的同时，密码学正在经历后量子迁移。这两个领域都需要重新面对拉宾提出的问题——随机性的边界在哪里？
大语言模型的训练依赖随机梯度下降，其输出本质上是概率分布的采样。这是拉宾式随机性的胜利，还是暴露了我们对"智能"理解的浅薄？当OpenAI的工程师调整temperature参数来控制模型创造性时，他们操作的是拉宾在1959年理论化的非确定性空间。
另一方面，NIST标准化的后量子密码算法（如CRYSTALS-Kyber和CRYSTALS-Dilithium）大量使用了拒绝采样（rejection sampling）等随机化技术。量子计算机威胁着RSA和椭圆曲线密码，但基于格（lattice）的替代方案仍然需要拉宾式的概率论证来保证安全性。
更深层的问题是：当计算能力持续指数增长，确定性算法与随机化算法的效率差距会扩大还是缩小？AKS素性测试的出现表明，理论上的差距可以缩小；但另一方面，随机化算法在近似计算、流数据处理、大规模优化等场景中的优势似乎正在扩大。
拉宾没有给出终极答案。他的工作价值恰恰在于将问题形式化，使其可以被后续研究者攻击。从这一角度看，"随机性是否必要"或许是个错误的问题——更好的问法是：在什么认知条件下，引入随机性能简化问题的表示或降低求解的成本？
拉宾的职业生涯跨越了计算机科学从边缘学科到核心基础设施的完整周期。他见证并参与了理论向实践的转化：1959年的自动机论文是纯粹的数学，1976年的素性测试已经触及工程应用，1980年代的不经意传输为商业密码学铺路，而零知识证明正在2020年代成为Web3的标配。
这种转化不是线性的。拉宾多次提到，早期工作被数学家忽视；直到复杂性理论成为计算机科学的核心课程，他的贡献才获得广泛承认。这提示我们：评估一项技术的长期价值，不能只看当下的应用场景，而要看它是否提供了新的问题表述方式。
对于25-40岁的科技从业者，拉宾的遗产有直接的实用维度。如果你在设计分布式系统，他的共识理论是必读背景；如果你在构建隐私保护产品，他的不经意传输和零知识证明是工具箱中的标准件；如果你在优化机器学习算法，他的概率分析方法提供了理论直觉。
但更重要的是思维层面的启发。拉宾展示了如何从具体场景（麦卡锡的间谍谜题）抽象出一般理论（计算复杂性层次），又如何将抽象理论（非确定性自动机）转化为可部署的技术（概率算法）。这种"场景-理论-工程"的三段跳，是产品创新者最稀缺的能力。
拉宾在希伯来大学时期的回忆值得反复咀嚼：「当时完全没有对计算问题研究的认可，数学家没意识到一个新领域正在诞生。」（"There was absolutely no appreciation of the work on the issues of computing. Mathematicians did not recognize the emerging new field."）这句话写于计算机科学已经建制化之后，但其中的张力至今存在：今天的"新领域"是什么？哪些正在被主流忽视的研究，将在三十年后成为基础设施？
可能的候选者包括：基于拓扑数据分析的机器学习、形式化验证与智能合约的结合、生物计算中的分子随机性、神经符号AI的交互证明系统。这些方向都涉及拉宾式的核心议题——如何在不确定性中建立可验证的确定性，如何用随机性来对抗复杂性。
拉宾的去世是一个时代的结束，但他的问题仍然开放。在量子计算、人工智能和去中心化系统的交叉点上，我们比任何时候都更需要理解：什么时候应该让计算机掷硬币，什么时候应该坚持确定性的路径？
如果拉宾的随机化范式最终被某种更深刻的理论所取代，那也将是通过他建立的问题框架实现的——正如AKS算法取代了米勒-拉宾在素性测试中的理论地位，却巩固了多项式时间可计算性作为复杂性理论的核心概念。
这就是理论计算机科学的奇特之处：它同时追求永恒和过时。拉宾的特定算法会被改进，但他的问题表述方式——非确定性作为计算资源、随机性作为证明技术、交互作为验证手段——已经成为我们思考计算的基本语法。
当下一版TLS协议部署、当某个zk-Rollup处理第100万笔交易、当某个AI模型通过概率采样生成一段看似有创意的文本时，拉宾的思想仍在运行。不是作为被引用的历史注脚，而是作为活的基础设施——如此基础，以至于使用者往往忘记它的存在。
这或许是理论研究者能期望的最好墓志铭：你的工作变得不可见，因为它已经融入了日常。
热门跟贴