2023/01/31 03:51 1270
在人工智能技术的支持下，今天的计算机可以与人进行令人信服的对话，作曲，绘画，下棋，诊断疾病，这只是它们技术实力的几个例子。
这些成功可以用来表明计算是没有极限的。要弄清楚情况是否如此，重要的是要了解是什么让计算机如此强大。
计算机的能力有两个方面:其硬件每秒可以执行的操作数量和运行算法的效率。硬件的速度受到物理定律的限制。算法——基本上是指令集——由人类编写，并转化为计算机硬件可以执行的一系列操作。即使计算机的速度可以达到物理极限，由于算法的限制，计算障碍仍然存在。
这些障碍包括一些计算机不可能解决的问题，以及一些理论上可以解决，但实际上却超出了当今最强大版本的计算机所能想象的能力的问题。数学家和计算机科学家试图通过在一台假想的机器上试验来确定一个问题是否可以解决。
一台虚构的计算机
现代算法的概念被称为图灵机，是由英国数学家艾伦·图灵在1936年提出的。这是一种虚构的装置，用来模仿用铅笔在纸上进行算术计算的方式。图灵机是当今所有计算机所基于的模板。
为了适应人工计算需要更多纸张的计算，图灵机中假想纸张的供应被假定为无限的。这相当于一条想象中的无限方块丝带或“带子”，每个方块要么是空白的，要么包含一个符号。
机器由一组有限的规则控制，并从纸带上的初始符号序列开始。机器可以执行的操作包括移动到相邻的方格、擦除符号和在空白方格上写入符号。这台机器通过执行一系列这样的操作来进行计算。当机器完成或“停止”时，留在纸带上的符号就是输出或结果。
计算通常是关于“是”或“否”的决定。类似地，医学测试(问题类型)检查患者的样本(问题实例)是否具有某种疾病指标(是或否答案)。实例，在图灵机中以数字形式表示，是符号的初始序列。
如果图灵机可以被设计为对每个实例都停止，无论其结果是正的还是负的，并且能够正确地确定实例产生的答案，那么这个问题就被认为是“可解决的”。
不是每个问题都能解决
许多问题可以用图灵机解决，因此可以在计算机上解决，而其他许多问题则不能。例如，多米诺骨牌问题，是华裔美国数学家王浩1961年提出的平铺问题的一种变体，是不可解的。
任务是使用一组多米诺骨牌覆盖整个网格，并遵循大多数多米诺骨牌游戏的规则，匹配相邻多米诺骨牌两端的点数。事实证明，没有一种算法可以从一组多米诺骨牌开始，并确定这组骨牌是否会完全覆盖网格。
保持合理
许多可解决的问题可以通过在合理的时间内暂停的算法来解决。这些“多项式时间算法”是有效的算法，这意味着使用计算机来解决它们的实例是可行的。
成千上万的其他可解决的问题还不知道有多项式时间算法，尽管正在进行大量的努力来寻找这样的算法。其中包括旅行推销员问题。
旅行商问题问的是，一组点与一些点直接相连的点(称为图)是否有一条路径，从任意一点开始，经过其他所有点只经过一次，然后回到原始点。想象一下，一个销售人员想要找到一条路线，该路线刚好经过一个社区的所有家庭一次，然后返回起点。
这些问题被称为np完全问题，在20世纪70年代初由两位计算机科学家——加拿大裔美国人斯蒂芬·库克和乌克兰裔美国人列昂尼德·莱文独立提出并证明了它们的存在。库克的工作是第一位的，他因此获得了1982年的图灵奖，这是计算机科学的最高奖项。
知道真相的代价
NP 完全问题最著名的算法本质上是从所有可能的答案中寻找解决方案。在一个由几百个点组成的图表上，旅行商问题需要在超级计算机上运行数年。这样的算法效率很低，这意味着没有数学上的捷径。
在现实世界中解决这些问题的实用算法只能提供近似，尽管近似正在改进。是否有有效的多项式时间算法可以解决np完全问题是克莱数学研究所在21世纪初发布的七个千年开放问题之一，每个问题都有100万美元的奖金。
在图灵
会有一种新的计算形式超越图灵的框架吗?1982年，诺贝尔奖得主、美国物理学家理查德·费曼(Richard Feynman)提出了基于量子力学的计算思想。
1995年，美国应用数学家彼得·肖尔(Peter Shor)提出了一种在多项式时间内分解整数的量子算法。数学家们认为，在图灵的框架下，这是用多项式时间算法无法解决的。一个整数因式分解是指找到一个比1大的能整除这个整数的整数。例如，整数688,8260,081可以被一个更小的整数25,253整除，因为688,8260,081 = 25,253 x 27,277。
一种被称为RSA的主要算法，广泛用于网络通信的安全，是基于分解大整数的计算难度。肖尔的结果表明，如果量子计算成为现实，它将改变网络安全的格局。
一个成熟的量子计算机能被用来分解整数和解决其他问题吗?一些科学家相信这是可能的。世界各地的几个科学家小组正在努力建造一个，一些人已经建造了小型量子计算机。
然而，就像之前发明的所有新技术一样，量子计算的问题几乎肯定会出现，从而带来新的限制。
本网站所发表这篇文章内容及图片来源于网络，仅用于交流使用，如有侵权请联系回复，我们收到信息后会在24小时内处理。