计算机变得越来越强大，能力越来越强，但一切都是有限的。 RYZHI/SHUTTERSTOCK

　　授权人 人工智能 技术，今天的计算机可以与人进行令人信服的对话(谢谢， 查特), 创作歌曲, 绘画玩 国际象棋和围棋 和 诊断疾病，仅举几个他们技术实力的例子。

　　这些成功可以表明计算没有限制。要了解情况是否如此，重要的是要了解是什么使计算机强大。

　　计算机的能力有两个方面：其硬件每秒可以执行的操作数量以及它运行的算法的效率。硬件速度受物理定律的限制。 算法 基本上是指令集，由人类编写，并转换为计算机硬件可以执行的一系列操作。即使计算机的速度可以达到物理极限，由于算法的限制，计算障碍仍然存在。

　　这些障碍包括计算机无法解决的问题，以及理论上可以解决但实际上甚至超出了当今最强大版本的计算机的能力的问题。数学家和计算机科学家试图通过在想象的机器上尝试来确定问题是否可以解决。

　　虚构的计算机

　　算法的现代概念，称为图灵机，由英国数学家于1936年提出 艾伦·图灵.它是一种虚构的设备，模仿用铅笔在纸上进行算术计算的方式。图灵机是当今所有计算机都基于的模板。

　　为了适应手动完成需要更多纸张的计算，在 图灵机 假定为无限制。这相当于一个想象中的无限丝带或正方形的“磁带”，每个正方形要么是空白的，要么包含一个符号。

　　机器由一组有限的规则控制，并从磁带上的初始符号序列开始。机器可以执行的操作是移动到相邻的正方形，擦除符号并在空白正方形上写入符号。机器通过执行这些操作的序列进行计算。当机器完成或“停止”时，磁带上剩余的符号是输出或结果。

　　计算通常是关于有是或否答案的决策。以此类推，医学测试(问题类型)检查患者的标本(问题的实例)是否具有某种疾病指标(是或否答案)。该实例以数字形式在图灵机中表示，是符号的初始序列。

　　如果图灵机针对每个实例(无论是正数还是负数)停止，并正确确定实例产生的答案，则问题被认为是“可解决的”。

　　不是每个问题都能解决

　　许多问题都可以使用图灵机解决，因此可以在计算机上解决，而其他许多问题则不能。例如，多米诺骨牌问题，这是美籍华裔数学家提出的平铺问题的变体。 王浩 在1961年，是无法解决的。

　　任务是使用一组多米诺骨牌覆盖整个网格，并按照大多数多米诺骨牌游戏的规则，匹配相邻多米诺骨牌末端的点数。事实证明，没有算法可以从一组多米诺骨牌开始，并确定该集是否会完全覆盖网格。

　　保持合理

　　许多可解决的问题可以通过在合理时间内停止的算法来解决。这些”多项式时间算法“是有效的算法，这意味着使用计算机来解决它们的实例是实用的。

　　数以千计的其他可解决的问题不知道具有多项式时间算法，尽管一直在努力寻找这样的算法。其中包括旅行推销员问题。

　　旅行推销员问题询问一组具有一些点直接连接的点(称为图)是否具有从任何点开始并恰好穿过每隔一点一次的路径，然后返回到原始点。想象一下，一个推销员想要找到一条路线，该路线正好经过一个社区中的所有家庭一次并返回起点。

　　这些问题，称为 NP完全，由两位计算机科学家独立制定并证明在 1970 年代初存在，美国加拿大人 斯蒂芬·库克 和乌克兰裔美国人 列昂尼德·莱文.库克的工作排在第一位，他因这项工作获得了1982年计算机科学界最高的图灵奖。

　　准确了解的代价

　　NP完全问题最著名的算法本质上是从所有可能的答案中寻找解决方案。几百个点的图表上的旅行推销员问题需要数年时间才能在超级计算机上运行。这样的算法效率低下，这意味着没有数学捷径。

　　不过，在现实世界中解决这些问题的实用算法只能提供近似值。 近似值正在改善.是否有有效的多项式时间算法可以 解决NP完全问题 是七人之一 千年开放问题 由克莱数学研究所在21世纪初发布，每个奖金为100万美元。

　　超越图灵

　　在图灵的框架之外，还有一种新的计算形式吗?1982年，美国物理学家 理查德·费曼诺贝尔奖获得者，提出了基于量子力学的计算思想。

　　1995年，美国应用数学家Peter Shor提出了一种量子算法 多项式时间中的因子整数.数学家认为，这是图灵框架中的多项式时间算法无法解决的。分解整数意味着找到一个大于 1 的较小整数，该整数可以除以整数。例如，整数 688，826，081 可被较小的整数 25，253 整除，因为 688，826，081 = 25，253 x 27，277。

　　一种称为 RSA 算法广泛用于保护网络通信，是基于分解大整数的计算难度。Shor的结果表明，量子计算如果成为现实，它将 改变网络安全格局.

　　能否构建一台成熟的量子计算机来分解整数并解决其他问题?一些科学家认为这是可能的。世界各地的几个科学家小组正在努力建造一个，有些人已经建造了小型量子计算机。

　　然而，就像以前发明的所有新技术一样，量子计算的问题几乎肯定会出现，这将带来新的限制。

　　王杰 是麻省大学洛厄尔分校的计算机科学教授。