← 暗能量充斥着宇宙，但它到底是什么今日好价 0322 →

3

再先进的AI也不能解决所有问题

受到人工智能技术的赋能，今天的计算机可以与人进行令人信服的对话(感谢ChatGPT)，创作歌曲、画画、下棋和围棋，诊断疾病，等等，这只是它们技术能力的几个例子。

这些成功可能会让人认为计算没有限制。要看是否如此，重要的是要理解是什么使计算机变得强大。

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

这些障碍包括计算机无法解决的问题和理论上可解决但实际上超出了今天最强大版本计算机能力范围的问题。数学家和计算机科学家试图通过在一个想象中的机器上尝试它们来确定一个问题是否可解。

想象中的计算机

现代对于算法的概念，称为图灵机，是由英国数学家Alan Turing在1936年提出的。它是一个想象中的设备，模仿了用铅笔在纸上进行算术运算的过程。图灵机是今天所有计算机都基于的模板。

为了适应手动完成时需要更多纸张的计算，在图灵机中假设想象中纸张供应无限。这相当于一条无限长或“无穷”的方格带或“纸带”，每个方格要么空白要么包含一个符号。

这台机器由一组有限的规则控制，并从纸带上的一个初始符号序列开始。机器可以执行的操作有移动到相邻的方格、擦除一个符号和在空白方格上写一个符号。机器通过执行这些操作的序列来进行计算。当机器停止或“停机”时，纸带上剩下的符号就是输出或结果。

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

如果图灵机对每个实例都能停机，无论正面还是负面，并正确地确定实例产生的答案，那么一个问题就被认为是“可解”的。

不是每个问题都能解决

许多问题可以用图灵机来解决，因此可以在计算机上解决，而许多其他问题则不能。例如，多米诺骨牌问题，由华裔美国数学家Hao Wang在1961年提出的铺砌问题的一个变体，就是不可解的。

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

保持合理性

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

还有数千个可解问题，尽管人们不断努力寻找这样的算法，但目前还没有已知的多项式时间算法。这些问题包括旅行商问题。

旅行商问题是问一个有一些点直接相连的点集，称为图，是否有一条路径从任意一点开始，恰好经过每个其他点一次，并回到原点。想象一个推销员想要找到一条路线，恰好经过一个社区里的所有家庭一次，并返回起点。

这些问题被称为NP完全问题，在20世纪70年代初由两位计算机科学家独立提出并证明了它们的存在，他们是美国加拿大人Stephen Cook和乌克兰裔美国人Leonid Levin。Cook的工作先于Levin，他因此获得了1982年图灵奖，这是计算机科学领域最高的奖项。

准确知道的代价

目前已知的NP完全问题的最佳算法本质上是从所有可能答案中搜索一个解决方案。在几百个点组成的图上运行旅行商问题可能需要超级计算机花费数年时间。这样的算法是低效率的，意味着没有数学上的捷径。

在现实世界中处理这些问题的实用算法只能提供近似值，尽管近似值正在改善。是否存在能够解决NP完全问题的高效多项式时间算法是21世纪初Clay数学研究所公布的七个千年难题之一，每个难题都悬赏100万美元。

超越图灵

是否存在一种超越图灵框架的新型计算方式？1982年，美国物理学家、诺贝尔奖得主Richard Feynman提出了基于量子力学的计算思想。

1995年，美国应用数学家Peter Shor提出了一个多项式时间的量子算法来分解整数。数学家们相信，在图灵框架中，这是一个无法由多项式时间算法解决的问题。分解一个整数就是找到一个大于1且能够整除该整数的较小整数。例如，整数688,826,081可以被较小的整数25,253整除，因为688,826,081 = 25,253 x 27,277。

一种被广泛用于保障网络通信安全的重要算法叫做RSA算法，它是基于分解大整数的计算难度而设计的。Shor的结果表明，如果量子计算能够成为现实，它将改变网络安全领域的格局。

能否建造出一个完全功能的量子计算机来分解整数和解决其他问题呢？有些科学家认为是可以的。世界各地有几个科学团队正在努力构建这样一台计算机，有些已经建造了小规模的量子计算机。

然而，就像之前发明过的所有新技术一样，量子计算也几乎肯定会遇到一些问题，这些问题会给它带来新的限制。

本文译自 HowStuffWorks，由 八里 编辑发布。

赞一个 (2)