在人工智能技术的支持下，今天的计算机可以与人进行令人信服的对话、 创作歌曲、绘画、下棋和诊断疾病，这只是其技术实力的几个例子。
这些成功可以用来表明计算没有限制。要了解情况是否如此，重要的是要了解是什么让计算机变得强大。
计算机的能力有两个方面：其硬件每秒可以执行的操作数和它运行的算法的效率。硬件速度受物理定律的限制。算法——基本上是指令集——由人类编写并转化为计算机硬件可以执行的一系列操作。即使计算机的速度可以达到物理极限，由于算法的限制，计算障碍仍然存在。
这些障碍包括计算机无法解决的问题，以及理论上可以解决但实际上超出当今可想象的最强大版本计算机能力的问题。数学家和计算机科学家试图通过在假想的机器上尝试来确定问题是否可以解决。
想象中的计算机器
算法的现代概念称为图灵机，由英国数学家艾伦图灵于 1936 年提出。这是一种模拟用铅笔在纸上进行算术计算的假想装置。图灵机是当今所有计算机的模板。
为了适应手动完成时需要更多纸张的计算，假定图灵机中的假想纸张供应量是无限的。这相当于想象中的无限条带或正方形的“带子”，每个正方形要么是空白的，要么包含一个符号。
该机器由一组有限的规则控制，并从磁带上的初始符号序列开始。机器可以执行的操作是移动到相邻的方格，擦除一个符号，并在空白方格上写一个符号。机器通过执行一系列这些操作来进行计算。当机器完成或“停止”时，留在磁带上的符号就是输出或结果。
计算通常是关于有或没有答案的决定。以此类推，医学测试（问题类型）检查患者的标本（问题的一个实例）是否具有某种疾病指标（是或否）。在图灵机中以数字形式表示的实例是符号的初始序列。
如果可以设计一个图灵机，它可以为每个实例（无论是正例还是负例）停止并正确确定实例产生的答案，则该问题被认为是“可解决的”。
不是所有问题都能解决
许多问题可以使用图灵机解决，因此可以在计算机上解决，而其他许多问题则不能。例如，多米诺骨牌问题是美国华裔数学家王浩于 1961 年提出的瓷砖问题的变体，是不可解的。
任务是使用一组多米诺骨牌覆盖整个网格，并遵循大多数多米诺骨牌游戏的规则，匹配相邻多米诺骨牌末端的点数。事实证明，没有一种算法可以从一组多米诺骨牌开始并确定该组是否会完全覆盖网格。
保持合理
许多可解决的问题可以通过在合理的时间内停止的算法来解决。这些“多项式时间算法”是高效的算法，这意味着使用计算机来解决它们的实例是实用的。
数以千计的其他可解决的问题并不知道有多项式时间算法，尽管人们一直在努力寻找这样的算法。其中包括旅行商问题。
旅行商问题问的是一组点与一些点直接相连，称为图，是否有一条路径从任何一点开始，每隔一个点恰好经过一次，然后回到原点。想象一下，一位推销员想要找到一条路线，该路线恰好经过一个街区的所有家庭一次并返回起点。
这些问题称为NP-complete ，由两位计算机科学家，美国加拿大人斯蒂芬库克和乌克兰裔美国人列昂尼德莱文独立制定并证明存在于 1970 年代初期。工作第一的库克因这项工作获得了 1982 年计算机科学最高级别的图灵奖。
确切知道的代价
最著名的 NP 完全问题算法本质上是从所有可能的答案中搜索解决方案。几百个点的图上的旅行商问题将需要数年才能在超级计算机上运行。这样的算法效率低下，这意味着没有数学捷径。
解决现实世界中这些问题的实用算法只能提供近似值，尽管近似值正在改进。是否存在可以解决 NP 完全问题的高效多项式时间算法是克莱数学研究所在 21 世纪之交发布的七大千年未解之谜之一，每门悬赏百万美元。
超越图灵
是否可以有一种超越图灵框架的新计算形式？ 1982年，诺贝尔奖获得者、美国物理学家理查德·费曼提出了基于量子力学的计算思想。
1995年，美国应用数学家Peter Shor提出了一种在多项式时间内分解整数的量子算法。数学家认为，这是图灵框架下的多项式时间算法无法解决的。因式分解一个整数意味着找到一个比可以整除该整数的整数更小的整数。例如，整数 688,826,081 可以被较小的整数 25,253 整除，因为 688,826,081 = 25,253 x 27,277。
广泛用于确保网络通信安全的一种称为RSA 算法的主要算法是基于分解大整数的计算难度。 Shor 的结果表明，如果量子计算成为现实，它将改变网络安全的格局。
能否构建成熟的量子计算机来分解整数并解决其他问题？一些科学家认为可以。世界各地的几组科学家正在努力建造一台，有些已经建造了小型量子计算机。
然而，就像以前发明的所有新技术一样，量子计算的问题几乎肯定会出现，从而施加新的限制。
本文根据知识共享许可从The Conversation重新发布。阅读原文。
图片来源： Laura Ockel / Unsplash