破解随机性“密码”的人：数学大神摘得2023年图灵奖

抛起一枚硬币，落地时哪一面会朝上？多数人认为“看运气”“五五开”。

真是如此吗？面对这一经典场景，美国普林斯顿大学教授维格德森（Avi Wigderson）指出，抛硬币或掷骰子，并不是真正随机的：如果你有足够的关于物理系统的信息，那么结果是完全可以预测的。完美的随机性是难以捉摸且难以验证的。

30年前形成的这一理论，彻底改变了计算数学对随机性的理解，对计算机科学的进步影响至深。

4月10日，有“计算机界诺贝尔奖”之称的图灵奖2023年获奖名单揭晓，花落维格德森。理由是他对计算数学基础的贡献，包括重塑人类对计算中随机性作用的理解，以及数十年来在理论计算机科学领域的领导地位。

图灵奖是计算机科学领域的最高荣誉。除了图灵奖之外，维格德森还与另一位学者分享了2021年的阿贝尔奖（Abel Prize），该奖项是数学界的最高荣誉。他也是唯一一位同时获得阿贝尔奖和图灵奖的人。

数学是计算机科学的基础

颁发图灵奖的美国计算机协会（ACM）主席雅尼斯·约安尼迪斯（Yannis Loannidis）在该组织发布的一份声明中表示：“数学是计算机科学的基础，维格德森的工作将广泛的数学子领域与理论计算机科学联系起来。”

维格德森因其在计算复杂性理论方面的工作而闻名，他主要研究随机性在计算中的作用。在上世纪90年代的一系列极具影响力的论文中，维格德森及其同事证明了计算在没有随机性的情况下也可以同样高效，并从那时起就塑造了算法设计。他的研究还包括协议设计和密码学，奠定了当今大部分数字基础设施的基础。

普林斯顿大学数学系教授许晨阳对第一财经记者表示：“维格德森做的领域属于计算复杂度，是数学和计算机交叉的领域。这些年他在纯数学领域的影响力也越来越大。”

计算复杂性理论所研究的，是资源中最常见的时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存），或者在并行计算中需要多少并行处理器才能解决问题。

维格德森于1999年加入普林斯顿高等研究院（IAS），并在那里建立了计算机科学和离散数学项目。在普林斯顿高等研究院的采访中，维格德森表示，自己既是一位数学家也是一位计算机理论科学家，研究的是计算领域的数学基础。

上世纪70年代，维格德森在以色列海法大学开始了大学生涯。最初他主修数学，但在父母的建议下转向了计算机科学。他的父母认为，这个专业更好找工作。

虽然未学成数学专业，但维格德森很快就发现，计算机科学是一个充满未解之谜的领域，而这些谜题，本质上都与数学相关。他早期的一项开创性工作，正是探讨一个看似矛盾的问题：能否在不展示证明过程的情况下让人相信，一个数学命题已经得到了证明？

在数学和计算机科学交叉领域的一系列发现中，维格德森的研究巩固了所谓的“零知识证明”理论，这在密码学和数字安全中至关重要。今天，零知识证明（Zero-KnowledgeProof，ZKP）技术已融入了隐私、合规性、身份验证和区块链技术等现代应用中。

普林斯顿大学计算机科学家拉齐（Ran Raz）评价维格德森称：“Avi在密码学领域有许多极其重要的成果，最重要的理论就是零知识证明。”

维格德森影响深远的论文包括：《Hardness vs. Randomness》（《对抗性与随机性》，与诺姆·尼桑（NoamNisan）合著）。这篇论文介绍了一种新型伪随机发生器，并证明了在比以前已知的假设更弱的条件下，可以对随机算法进行高效的确定性模拟。

维格德森这些理论的影响远远超出了随机性和去随机化领域，被应用于理论计算机科学更广泛的领域，且激发了该领域多位领军人物发表具有影响力的论文。

他的工作融入今天人们的日常生活

菲尔兹奖首位华人得主丘成桐对第一财经记者表示，维格德森获得图灵奖并不意外，因为与其称他为一位数学家，维格德森更是一名计算机学家，他的主要研究领域是计算机方面的工作。“当然数学是一切科学理论的基础。”丘成桐表示。

理论计算机科学专注于计算领域的数学基础，理论计算机科学还致力于设计高效的算法。事实上，每一项触及我们生活的计算技术都是通过算法实现的。深入理解构成强大和高效算法的原理，不仅能增进人们对计算机科学的认识，还能帮助人们更好地理解自然规律。

随机性基本上是一种在不知道最优解的情况下，确保对最优解有正确了解的方法。随机性在计算机科学中找到了无数其他用途，从密码学到博弈论到机器学习。

值得关注的是，2017年谷歌向普林斯顿IAS注资，开始研究新的机器学习的方法。谷歌高级副总裁JeffDean表示，维格德森的研究几十年来“奠定了理论计算机科学的发展进程”，而他的工作也直接融入了人们的日常生活。

第一财经记者注意到，去年11月，受2000年图灵奖得主、清华大学交叉信息研究院院长姚期智邀请，维格德森刚刚到访过清华大学交叉信息研究院，进行了“模仿游戏”源流和应用的学术讲座。

姚期智当时在介绍维格德森时说道：“我和维格德森已经相识40多年，都从事计算机理论研究，Avi在理论方面已形成了独到洞见。”

姚期智的研究方向包括计算理论及其在密码学和量子计算中的应用。他用计算机发牌、打牌，研究计算机理论，并将这种理论应用到密码学。用通俗的比喻来讲，生意合伙人如果互相发送电子邮件，即便使用只有双方通晓的暗语，也存在泄密的可能，这就牵涉到信息安全和加密，这些方向与维格德森的研究也高度重合。

在去年11月的那场报告中，维格德森从阿兰·图灵提出“图灵测试”出发，叙述了“模仿学习”理论在密码学、随机性、离散数学、数论等领域的现代应用。他基于凯撒密码（Caesar’s Cipher）、恩尼格玛密码机（Enigma machine）、选举（secure elections）等案例，引导学生思考安全性的定义、随机性的应用、隐私和效用的平衡等问题。

他还回应了AI大型大语言模型出现后，会对理论计算机研究的发展方向产生什么样的影响。对于理论计算机研究将如何应对人工智能发展这一问题，维格德森表示：“尽管包括大语言模型在内的人工智能有很多惊人表现，但最重要的问题是AI还有哪些是不能做的。我相信人工智能发展过程中总有天花板。”

维格德森还称，自己曾为解决一个开放性问题花了40年时间，并建议学生要选择自己喜欢的研究领域，享受在失败中不断学习的过程，这样才能在科研道路上走得长远。