即使是先进的人工智能也不能解决所有问题

由:洁王|
人工智能"width=
计算机变得越来越强大,能力越来越强,但一切都有极限。Ryzhi /伤风

授权的人工智能今天的技术,计算机可以与人进行令人信服的对话(谢谢,ChatGPT),创作歌曲油漆绘画,玩国际象棋和围棋而且诊断疾病这只是他们技术实力的几个例子。

这些成功可以用来表明计算是没有极限的。要弄清楚情况是否如此,重要的是要了解是什么让计算机如此强大。

广告

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

这些障碍包括一些计算机不可能解决的问题,以及一些理论上可以解决,但实际上甚至是当今最强大版本的计算机都无法解决的问题。数学家和计算机科学家试图通过在一台假想的机器上试验来确定一个问题是否可以解决。

广告

虚构的计算机

现代算法的概念,即图灵机,是由一位英国数学家在1936年提出的阿兰·图灵。这是一种虚构的装置,用来模仿用铅笔在纸上进行算术计算的方式。18新利最新登入图灵机是当今所有计算机所基于的模板。

为了适应人工计算时需要更多纸张的计算,a中虚构纸张的供应图灵机假设是无限的。这相当于一个想象的无限的方块丝带或“带子”,每个方块要么是空白的,要么包含一个符号。

广告

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

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

如果图灵机在每个实例中都停止,无论结果是正的还是负的,并正确地确定实例产生的答案,那么这个问题就被认为是“可解决的”。

广告

不是每个问题都能解决

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

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

广告

保持合理

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

成千上万的其他可解决的问题还不知道有多项式时间算法,尽管正在进行大量的努力来寻找这样的算法。其中包括旅行推销员问题。

广告

旅行商问题问的是,一组点与一些点直接相连的点(称为图)是否有一条路径,从任意一点开始,经过其他所有点只经过一次,然后回到原始点。想象一下,一个销售人员想要找到一条路线,该路线刚好经过一个社区的所有家庭一次,然后返回起点。

这些问题叫做非完全多项式在20世纪70年代初,两名加拿大籍美国人计算机科学家独立制定并证明了它的存18新利最新登入在斯蒂芬·库克乌克兰裔美国人列昂尼德•莱文。库克的工作是第一位的,他因此获得了1982年的图灵奖,这是计算机科学的最高奖项。

广告

了解真相的代价

np完全问题最著名的算法本质上是从所有可能的答案中寻找解决方案。在一个由几百个点组成的图表上,旅行商问题需要在超级计算机上运行数年。这样的算法效率很低,这意味着没有数学上的捷径。

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

广告

在图灵

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

1995年,美国应用数学家彼得·肖尔(Peter Shor)向以多项式时间分解整数。数学家们认为,在图灵的框架下,这是用多项式时间算法无法解决的。一个整数因式分解是指找到一个比1大的能整除这个整数的整数。例如,整数688,8260,081可以被一个更小的整数25,253整除,因为688,8260,081 = 25,253 x 27,277。

广告

一个主要的算法叫做RSA算法,广泛用于网络通信的安全,是基于分解大整数的计算难度。肖尔的结果表明,如果量子计算成为现实,它将会改变网络安全的格局

一个成熟的量子计算机能被用来分解整数和解决其他问题吗?一些科学家相信这是可能的。世界各地的几个科学家小组正在努力建造一个,一些人已经建造了小型量子计算机。

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

洁王他是马萨诸塞大学洛厄尔分校计算机科学教授。

本文转载自谈话在创作共用许可下你可以在原文在这里。

广告

特色

广告

加载……
Baidu