计算的局限性：一位计算机科学家解释了为什么即使在人工智能时代，有些问题也太难了

在人工智能技术的支持下，今天的计算机可以与人进行令人信服的对话，创作歌曲，画画，下棋，诊断疾病，这只是其技术实力的几个例子。

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

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

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

虚构的计算机

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

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

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

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

如果可以设计一个图灵机，它为每个实例（无论是正数还是负数）停止，并正确确定实例产生的答案，则问题被认为是“可解决的”。

不是每个问题都能解决

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

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

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

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

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

这些问题被称为NP完全，由两位计算机科学家，美国加拿大人Stephen Cook和乌克兰裔美国人Leonid Levin在1970年代早期独立提出并证明存在。库克的工作排在第一位，他因这项工作获得了1982年计算机科学界最高的图灵奖。

确切了解的成本

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

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

超越图灵

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

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

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

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

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