抱歉ChatGPT，有些问题对AI来说总是太难了

在人工智能技术的支持下，如今的计算机可以与人进行令人信服的对话，创作歌曲，绘画，下棋和围棋，诊断疾病，仅举几个例子来说明其技术实力。

这些成功可以被视为表明计算没有限制？要了解这是否属实，重要的是要了解是什么使计算机强大。

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

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

虚拟计算机

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

为了适应人工计算需要更多纸张的情况，假设图灵机中虚拟纸张的供应是无限的。这相当于一条假想的无限带状或“带状”正方形，每个正方形要么是空白的，要么包含一个符号。

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

什么是图灵机？

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

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

并非所有问题都能解决

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

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

保持合理

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

尽管目前正在努力寻找多项式时间算法，但仍有数千个其他可解问题没有多项式时间算法。其中包括旅行推销员问题。

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

当你离开几个目的地时，旅行推销员问题很快就失控了。

这些问题被称为NP完全问题，是由两位计算机科学家在20世纪70年代初独立提出并证明存在的。

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

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

什么是量子计算机？

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

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

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

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