美国计算机协会(ACM)周三宣布授予今年的A.M.图灵奖，通常被称为计算领域的诺贝尔奖，授予普林斯顿高等研究院的计算机科学家和数学家Avi Wigderson。
美国计算机协会表示，维格森因在推进所谓的计算理论方面的基础性贡献而获得认可，尤其是在“重塑我们对随机性在计算中的作用的理解”和“在理论计算机科学领域数十年的智力领导”方面的杰出贡献。
该奖项以英国数学家和计算机科学家艾伦·图灵的名字命名，奖金为100万美元，由谷歌提供资金支持。
普林斯顿大学赫伯特·h·马斯(Herbert H. Maass)教授威格森(Wigderson)几十年来对计算的深刻理解不仅仅是机器。计算是宇宙中普遍存在的现象。
“计算是一个非常基本的概念，”Wigderson在接受ZDNET采访时说。“不只是计算机中的算法:所有东西都可以计算。”
“当你在海滩上看到一个贝壳，它有一些非凡的图案，这是通过非常简单的步骤计算出来的:它从一个颗粒生长，在局部，这些颗粒计算相邻的颗粒，并连接在一起——这个非常简单的过程，你进化它，你会得到一些惊人的图案。”
Wigderson说:“我们非常了解这些地方性的、渐进式变化的简单规则，它们可以产生非常复杂的现象。”计算例子比比皆是。计算是指受精卵如何成为一个人，或者人类细胞如何在一个人的一生中分裂。“还有，流言蜚语。”威格森补充说。“当你说出别人告诉你的东西时，或者在Facebook上——信息的发展方式，这些都是计算问题，可以用完整的计算模型来构建。”
把图灵奖颁给威格森是再合适不过的了，因为他的研究领域——计算理论——是由图灵在1936年发表的具有里程碑意义的论文《论可计算数，及其对可计算性问题的应用》开创的。
图灵为计算这个极其宽泛的定义奠定了基础，计算是通过局部的、增量的变化对环境进行演化，其中的“环境”可以是人类、星系、海滩上的贝壳、信息或任何数量的现象。
从图灵的角度来看，每一个自然现象都是计算，这是威格森和他的同事几十年来提出的。威格森解释说:“白蚁是如何建造这些城堡的，或者蜜蜂是如何知道去哪里寻找蜂蜜的——它们实际上是如何进化创造的，尽管它们的脑细胞非常小。”
该奖项特别表彰了Wigderson对理解随机性在计算中的作用所做的贡献。传统计算机，从大型机到iphone，都是“确定性的”;也就是说，它们遵循一种可预测的步骤模式。但是，自然界中许多最有趣的计算例子都涉及随机性元素，从贝壳到被称为“杂音”的椋鸟群。
威格森和他的合作者利用对随机性的探索，加深了对哪些问题可以“有效”计算、哪些问题不能“有效”计算的理解。世界上有许多问题——在科学、数学和工程领域——都没有已知的有效算法，这意味着一种算法可以在“多项式时间”而不是指数时间内运行。
例如，将大整数分解成它们的质因数，目前还没有一种已知的算法可以在低于指数级的时间内运行。但仅仅找到这样一个算法是不够的;计算机科学家和数学家想要证明，想要确定地知道，无论如何，是否存在这样一个“难”问题的解决方案。
Wigderson告诉ZDNET, ACM引用的三篇主要论文形成了一个序列，一个级数。
“问题是算法中的随机性有多强大，”威格森说。从80年代开始，计算机科学家发现了许多利用随机性作为高效算法的途径，“因此，随机性看起来非常强大。”
“这些研究旨在表明，随机性并没有那么强大，”他说。取而代之的是，威格森和他的同事们开发了伪随机数生成器，可以以一种有效的、确定的方式解决一些难题。
“在所有这些论文中，你都要解决一个难题，然后创建一个伪随机生成器，它可以确定地生成看起来随机的比特，你可以用概率算法替换随机输入，(并形成)一个确定性的输入。”
淘汰随机性，代之以确定性方法，最终论文中出现了最复杂的伪随机生成器。Wigderson指出:“我们可以得出结论，任何多项式时间的概率算法都可以变成多项式时间的确定性算法。”
这些发现的一个令人惊讶的副作用是，如果你可以从算法中去除随机性，你就可以证明问题的难度——这是一种解决问题是否困难的引人注目的后门方法。
Wigderson说:“这两个概念(随机性和硬性)虽然非常不同，但却紧密相连。”“它们几乎是一样的。从概率算法中去除随机性，并证明计算问题的难度，在某种程度上是双重问题。”
对于那些希望更深入地研究随机性的人，下面列出了这些论文。然而，你可以在威格森的大书《数学与计算》中阅读关于随机性的章节，这本书可以免费下载。如果你把这本书略读一下，你就会在下次鸡尾酒会上比大多数人都强。
对于67岁的威格森来说，从很小的时候起，找出令人惊讶的联系的乐趣就是一种驱动冲动。
“我从小就喜欢数学，”威格森说。“我爸爸对拼图之类的东西很感兴趣。”
Wigderson毕业于以色列理工学院(Technion Institute of Technology)，并在普林斯顿大学获得计算机科学硕士和博士学位。去年，威格森在接受以色列理工学院荣誉博士学位的获奖感言中谈到了他的经历。
“我真的很关心计算模型的形式化，”威格森谈到他感兴趣的东西时说，“比如，某种加密协议是否安全，或者某种算法的运行时间是否安全。
“它处理的是这个基本概念，但它实际上是一个数学领域，这对我来说非常宝贵。”
威格森说，他最引以为傲的成就之一是他推进了所谓的“零知识证明”，即信息可以保密，但交易双方仍然可以达成谅解。“假设我知道一些事情，我知道谁会赢得选举，而你不相信我，我正试图说服你(我真的相信)。我有个办法可以说服你，而不用告诉你任何你不知道的事。”
事实上，这种情况是公钥密码学的根源，其中每一方都隐藏自己的私钥，但能够说服另一方他们已经权威地签署了电子合同，例如。“这是一个完全矛盾的概念，”威格森谈到这种零知识证明时说。“想到这样的东西可能存在，这种事情会让你大吃一惊。”
威格森的智慧平衡了愉悦与对潜在意义的敏锐感知。例如，哪些问题可以证明是困难的，这个问题对社会有很大的利害关系。
正如20世纪70年代提出的，“P = NP吗?”这个短语问的是，如果一个问题的解可以被验证，那么这个问题最终是否也可以用一个多项式时间方程来解决——而且是有效地解决。如果是这样，那么计算机很可能在实际的时间跨度内解决世界上一些看似棘手的问题。
“这是有史以来最基本的智力问题之一，”P = NP的Wigderson说。他的个人猜想是P不等于NP，这是他所在领域的共识，也就是说，有些问题是无法有效解决的。
“如果每个人都错了，P等于NP，它会产生惊人的后果，”Wigderson说。“几乎任何你想解决的问题，你都能有效地解决——任何问题;你可以治愈癌症。”
然而，“如果P不等于NP，对我们无法达到的事物的影响是相当重要的，”Wigderson说。首先，这意味着人类思维的一些要素，比如创造力，可能是计算机无法企及的，因为没有办法有效地模拟启发式，即人类对事物的感知，比如艺术创作。
但在另一种意义上，杯子是半满的:如果NP问题不能有效地解决，这意味着密码学——现代经济的整个基础——是安全的，不会被破解，Wigderson指出。
P是否等于NP是一个悬而未决的问题。威格森说:“我曾希望在我有生之年看到有人证明这一点，但现在我怀疑这一点。”
量子计算机也不是打破这一僵局的简单答案。“想想量子计算机:这是不存在的，”威格森说。“我们不知道它是否会存在”——尽管IBM、谷歌和其他公司对它进行了激烈的理论化。
如果P = NP是一个开放的问题，那么当下的问题也是:人工智能(包括“通用人工智能”机器)能做什么或不能做什么，才能与人类的思维匹敌?当然，宇宙万物都可以计算的概念意味着人工智能应该能够达到某种程度的人类能力。
“我们是碳，而他们是硅，所以材料是不同的，但困难是在心理层面，而不是在操作层面，”威格森认为。威格森说，人工智能已经证明，它“可以解决许多我们以前不知道如何解决的问题”。他知道“一些杰出的数学家开始使用这些设备作为合作者”在定理证明等方面。
“我更感兴趣的是他们做不到的事情，”他说。“这种类型的计算机有什么限制?”其中一个限制是训练人工智能模型解决某些问题所需的数据相对缺乏。
“例如，设计一个新的数学理论，比如相对论或麦克斯韦方程——对于这些，例子要少得多，对吧?”所以，我认为这种理论突破对于这些机器来说将会更加困难，因为没有那么多的数据。”
对于P等于或不等于NP的许多含义，Wigderson很满足于让新一代引领潮流。
“我和研究所的博士后们在一起很开心，他们都很聪明，我和他们中的一些人合作，向年轻人学习，”他说。“在这种情况下，周围都是年轻人，让你不断学习，这很好。”
