Episode 10: What Use is Computational Theory?
41:31 Share

任何理论播客都需要您的帮助。我们拥有一小群忠实的听众，我们希望向其他人宣传播客，以便其他人也能欣赏它。据我们所知，我们是唯一一个涵盖戴维·杜伊奇哲学所有四个方面以及其他有趣主题的播客。如果您喜欢这个播客，请在 Apple Podcasts 上给我们五星好评。这通常可以在您的播客播放器中直接完成，或者您可以搜索“任何理论播客 Apple”之类的关键词。

有些播放器有自己的评分系统，在任何评分系统上给我们五星好评都会有所帮助。如果您喜欢某一集，请考虑发推文或在 Facebook 或其他社交媒体上链接到我们，以帮助宣传。

如果您有兴趣在经济上支持播客，我们有两种方法可以做到这一点。第一种是通过我们的播客托管网站 Anchor。只需访问 anchor.fm/four-strands，F-O-U-R-S-T-R-A-N-D-S。有一个支持按钮，允许您进行定期捐款。如果您想进行一次性捐款，请访问我们的博客 fourstrands.org。那里有一个使用 PayPal 的捐款按钮。

谢谢。欢迎回到“任何理论”播客。卡梅奥，你好吗？我很好，布鲁斯。你好吗？很好。心情很好。我们今天有一集好节目，虽然它比我们过去做的一些节目更技术性一些。所以我将挑战自己，尝试使更技术性、更面向数学的主题仍然令人兴奋。

最后你可以评价我做得怎么样。嗯，我认为你不应该太依赖视觉效果，这使得描述复杂事物而不依赖视频增加了额外的复杂性。是的。所以，这将是一个小小的挑战，但我认为我们可以做到。所以……

好了，我们开始吧。就像上一集一样，我们谈到了计算理论，这是我最喜欢的主题之一。事实上，我回到学校学习人工智能，就是因为它与计算理论的联系。我今天会稍微谈谈这个，谈谈我是如何对这个感兴趣的。

但在上一集里，我们谈到了图灵机和丘奇-图灵论题。我简要地提到了图灵原理。但是今天，我将尝试向你解释，我们在现实生活中究竟如何使用计算理论？研究人员会用它做什么？并给你一个概述这个领域是什么，如果这说得通的话。所以……

我们将从一些比较简单的事情开始。你小时候或高中时做过编程吗？你知道，大约在我9或10岁的时候，我们有一台 Commodore 64。对。是的，你会制作一些小程序，这些小程序会……

通常生成视觉效果或，你知道，逐步增加数字……是的，完全是的，是的，所以我有一台 Commodore 64 和一台 TI-99-4A，并学习了这两个程序的编程，这实际上是我开始接触计算机的原因，所以……你记得高中时或类似的事情吗？在你的脑海深处，有什么叫做冒泡排序的东西吗？

不，不一定是。我的意思是，我后来学过它，但我记不得学过它了。好的，但是你知道它是什么吗？是的。好的，我们将讨论冒泡排序。所以我们有一列整数，实际上只是 0 到 9，但它们是无序的，我们想把它们按顺序排列。好的，我们将想出如何做到这一点，一系列步骤。这就是算法或程序，是一系列步骤。好的。

按顺序排列它们。所以我们可能这样做的一种方法是冒泡排序，从概念上来说非常容易，但不一定是速度最快的方法。你会做的就是简单地比较前两位数字，然后交换它们的位置，使它们有序。然后你只需遍历这一行，不断地一次比较两个数字，如果需要就交换它们。

好的。所以你只需不断地这样做。我在屏幕上这样做。我得到了开始时无序的数字。当你到达结尾时，它们仍然没有顺序。但是它们现在比以前更有序了。好的。它们仍然没有顺序。很好。好的。

所以我们遍历了每一个数字，并一次比较相邻的两个数字。有 10 个数字，所以有 9 次比较，因为你一次比较两个。所以我问你的问题是，你需要多少次比较才能对整个列表进行排序。

为了帮助你理解这一点，我希望你从两个方面考虑这个问题。想想如果列表已经排序好了，对列表进行排序需要多少次比较？在这种情况下，为了确保你已经对列表进行了排序。如果列表一开始是反向排序的，那么对列表进行排序需要多少次比较？所以考虑一下。嗯，你

你知道，我最初的直觉反应是，数字的顺序不应该影响我需要对列表进行排序的比较次数。

必须进行比较才能验证数字或进行比较。但我可能有点迟钝。好的，让我们从这个开始。让我们选择有序的那个。好的，所以是 0 到 9。在你的脑海里做。多少……所以它们已经有序了。所以很明显，正确的答案是它不需要比较。但是计算机不知道这一点。它必须遍历并进行冒泡排序比较才能弄清楚……

它们是有序的，我可以停止了？七。很好的猜测。实际上是九。

所以基本上，这与我刚才在屏幕另一侧显示的完全相同。对。遍历一次。一旦你遍历一次并且没有改变任何一个，那么它就知道完成了。它说，好的，足够了。对。好的。所以如果列表是有序的，则需要 9 次比较。现在大胆猜测一下，如果列表是反向排序的，你需要多少次比较。所以这实际上是它的最坏情况。

好的。27。很好的猜测。谢谢。所以如果你仔细考虑一下，它实际上是，你必须遍历列表进行这些，9 次。所以遍历列表一次需要 9 次比较。你必须遍历列表 9 次。是的。所以在这种情况下，将是 81 次比较。好的。是的，这说得通。好吧。我应该多考虑一下。

那么，这算出来是什么呢？嗯，这实际上是数字的数量减一，因为比较次数总是比数字的数量少一，平方。好的，这是最坏情况下所需的比较次数。好的。现在，平均而言，它已经部分排序了。所以也许需要一半的时间。好的，但是……

它将接近，你知道，这是最坏的，这是界限。这是最坏的情况。而且通常不会好多少，对吧？我的意思是，81 的一半更接近 81，更接近 81 而不是 9，对吧？你很少得到最佳情况，如果这说得通的话。对。所以我们可能会将其列为 X 减一平方，或者减一，我们可以忽略它。

好的，在计算理论中，我们并没有真正关注细节，因为如果有 100 万个数字，你试图对它进行排序，那么算法所需的时间不会有太大区别

如果是 100 万或 100 万减一，对吧？从人类的角度来看。所以他们做的是所谓的“大O表示法”，他们说，好的，X 减一平方，我们将称之为与 X 平方相同。好的。所以为了评估这个算法及其速度，我们将称之为 X 平方算法。好的。这说得通吗？是的，绝对说得通。好的。

好的。那么我们现在能用它做什么呢？好的。所以我已经向你介绍了我们如何得出算法的“速度”的基本知识。好的。现在关于这一点有一些奇怪的地方，一开始可能并不明显。我们通常不会谈论，我的意思是，我们通常会谈论，如果我们是外行，我们可能会谈论计算机的速度，但在这里我们谈论的是算法的速度。好的。那么它们之间是什么关系呢，计算机的速度和算法的速度？嗯，

嗯，我们在上一集谈到了丘奇-图灵论题。当时我说的是，好的，这实际上意味着什么。记住，它不是一个，它没有被证明，但它是一个科学理论。我认为它是经过最佳测试的科学理论。好的。对。它说，

不可能设计出任何类型的计算机器，它能够执行一台普通的图灵机无法执行的逻辑程序，并且图灵机及其等价物是最强大的计算机器，而且没有比这更强大的机器了。我们甚至谈到了这样一个事实，即这并不完全正确，因为我们后来发现了量子计算机，但我们暂时忽略这个事实。

如果这两个陈述是正确的，那么关于这个论题还有什么其他的是正确的呢？嗯，关于这个论题正确的一点是，所有计算机器在功能上都是等价的。好的。暂时忽略量子计算机。好的。这意味着如果你知道图灵机执行计算需要多少次计算，那么所有计算机器都需要同样多的计算。

是的。好的。因为图灵机实际上是一台通用计算机。好的。这就是丘奇-图灵论题所说的。所以当我们谈论算法的速度时，这是一个有意义的陈述，对吧？是的。你可能有一台速度更快或更慢的计算机，是的，这会产生影响，但算法的速度与

任何特定的计算设备无关。它是给定输入大小的计算次数。在这种情况下，是数字的数量。它是完成该算法所需的计算次数。好的，如果你有一台非常非常快的计算机或一台非常非常慢的计算机，它显然会更快地进行计算，但它仍然需要这么多次计算。

所以让我们以一个具体的例子为例，顺便说一句，对于那些可以看到屏幕的人，我有这个，这个我从维基百科上抓取的图片，它实际上显示了冒泡排序的过程。我认为这很酷。所以我决定把它包含进来，这样你就可以从概念上了解它在做什么。但是如果我们正在进行冒泡排序，输入是 X，数字的数量和我们试图排序的数字的数量，我想我们试图排序的数字的数量。并且，并且，

X 平方是计算次数。那么多少次计算，这很容易。对 10 位数字进行排序需要多少次计算？对不起，我迷路了。我一直在看那个小动画。

所以，你知道，我们已经说出了这个问题的答案。是 81。好的，我以为是的。好的，但请记住，我们使用大O表示法进行近似。所以如果它是一个 X 平方算法，并且是 10 位数字，你知道，输入大小是 10，那么我们将其近似为 X 平方是多少次计算？10 平方。还在看动画。它真的很棒。是的。

显然是 100 次计算，我们预计它会进行大约 100 次计算。好的。现在，由于这个平方，这将呈指数级增长。所以如果是 100 位数字，那么我们谈论的是 10,000 次计算。如果是 1,000 位数字，那么我们谈论的是 100 万次计算。好的。所以……

有趣的是，随着输入大小的增长，是的，一台更快的计算机正在更快地进行这些计算，但它并没有，你可以很快超过任何计算机的速度，对吧？你可以很快达到这样一个点，你有一个计算，它只是简单地需要，你知道，算法，这么多次计算，并且，

它根本不取决于你的计算机有多快。对，对。这实际上是计算理论的真正意义所在。它是研究我们实际上能够计算什么？物理定律允许我们计算什么？对于某些类型的算法来说，它们是不可处理的，对吧？有些是，正如我们将看到的，有些实际上是完全不可计算的。但是我将

有很多算法是不可处理的，除非你正在对算法的输入大小进行非常非常小的处理，换句话说，你只是试图对少数数字进行排序或类似的事情。无论你的计算机有多快，算法都太慢了，无法计算得太远。事实上，这实际上就像，你想想，比如，

计算机下棋，好的，深蓝或类似的东西，对吧？嗯，

国际象棋依赖于这样一个事实，即游戏是不可处理的，对吧？理论上，我们知道如何解决国际象棋。我们知道你只需要向前看，并在你的脑海中，在计算机的脑海中，比如说在它的内存中，做出所有可能的移动。然后你从每一个移动中，尝试你对手可能尝试的每一个移动。然后你尝试之后每一个移动。你只需继续下去。如果你，理论上，如果你有一台计算机，它

有足够的内存和，嗯，并且速度足够快，你实际上可以解决国际象棋，那么游戏将变得毫无趣味，对吧？你会从第一步开始就知道你会赢，你知道，或者你会知道不可能赢。嗯，

所以游戏是不可处理的事实，即任何计算机都永远无法解决它，这使得它，你知道，任何人都无法解决它，这使得它变得有趣。好的。生活中有很多事情实际上依赖于这样一个事实，即有很多很多很多事情是不可处理的，你根本无法计算。好的。深蓝实际上是如何下棋的呢？嗯，它所做的是传输

试图尽可能多地向前看几步。随着我们为计算机添加更多内存和更快的速度，它可以开始向前看更多步，你知道，它可以慢慢地开始向前看更多步。如果它能看到，比如说，6 或 7 步，它就能击败任何人，对吧？

但这就像最，而且比这更复杂。他们实际上使用一些技巧，以便他们能够弄清楚如何不查看某些前进的路径，而只关注最有趣的路径。然后他们试图向前看 10 步或类似的东西。对。但即使在最好的情况下，计算机也无法向前看那么多步。它就是做不到。对。因为它从计算的角度来看是一个不可处理的问题。所以是的，

现在，我们正在查看冒泡排序。现在，冒泡排序不是最快的排序。实际上有一种叫做快速排序的东西，它比冒泡排序快得多。并且计算量不会随着输入大小的增长而增长得那么快。但我们实际上有比 X 平方差得多的算法。事实上……

即使我们有像 X 的 100 次方这样的算法，这将是一个糟糕的算法，不可否认，但这仍然不是最坏的情况。最坏的情况是当你翻转

常数和输入大小。所以现在我们正在处理输入大小为 X 平方的情况，这是一个常数。2 是一个常数，对吧？想象一下，如果将其翻转，使得算法具有常数 2，然后输入大小 X 是幂。所以是 2 的 X 次方，而不是 2 的 X 次方，好的？这就是我们所说的指数时间算法，好的？而且有很多这样的算法。并且

只是看看我的屏幕，如果你可以看到屏幕，一个大O X 平方，输入大小为 100，是 100 平方或 10,000 次计算，而

2 的 X 次方。所以现在我们已经翻转了指数和，指数现在是变量，常数现在是我们提升幂的东西。让我们把它调到 100。看看它的规模。我甚至无法说出这个数字的名称。它太大了，对吧？甚至没有一个词来形容它。是的。所以，我的意思是，它，

我们有算法是如此难以处理，超过一定的输入大小，我们永远不会有一台计算机能够解决它，对吧？这就是指数时间算法。事实上，有很多，而这实际上在哲学上非常有趣。我们生活中有很多事情想要做，实际上是指数时间算法。

例如，举个例子，我们可以就此做一个单独的播客，因为我发现有一本书对此进行了非常引人入胜的描述。你是一个非常忙碌的人，卡梅奥。你在工作和职业生涯中有很多事情想要完成。那么问题是什么呢？是的，阿门。你将面临的一个问题是，我接下来应该做什么才能

让我完成我想要完成的事情中的大部分。好的。这是一个，这是一种算法。你可能不认为这是一个算法，但它确实是，你正在采取步骤来选择它，决定这是我接下来需要做的最重要的事情。好的。计算出对你来说真正最重要的事情，以便你能完成最多的事情，这是一个指数时间算法。所以你永远不可能完全正确地做到这一点。

对。不，我，你知道，实际上我们应该把它放在未来的剧集中，因为我还认为在某种技术开发产品管理中，优先考虑功能方面。在这个领域也是一个非常有趣的讨论。

是的，是的。我认为很多东西都与软件开发有关，顺便说一句。事实上，计算理论与认识论以及我们在软件中所做的事情之间有着密切的联系。所以现在只是一些快速术语。

如果我们谈论的是大O X，那么输入大小，计算次数与输入大小的增长完全相同，与输入大小的增长长度相同。为了论证起见，大O，记住它会忽略我们不太关心的东西。所以也许是输入大小的 10 倍或类似的东西，对吧？我们不在乎，因为 10 倍不足以让我们担心。我们将称之为线性时间。

如果是 X 的常数次方，X 的平方，X 的某个常数次方，我们称之为多项式时间。如果你还记得你的高中代数，多项式，它们是你试图像写 X 平方加 Y 的三次方等于零或类似的东西。对。我们称之为多项式。所以这叫做多项式时间。这就是指数是一个常数的地方。对。

然后指数时间是指指数是变量的地方。好的。这说得通吗？是的。是的。所以指数时间是最难的。它们是……

嗯，你知道，也许我们希望有这些问题的答案，但除了非常小的规模之外，没有办法完美地计算它们。好的。嗯，他们实际上创建了算法的类别。如果你在 YouTube 上观看这个视频，你可以看到屏幕。嗯，

并且，想象一下，这里的外圆，想象一个外圆做一个维恩图，它代表所有可能的算法。所以无限数量的那些，但所有可能的算法都由外圆表示。好的。现在有一组算法是决策问题。所以决策问题将是一个算法，你得到，它会返回对某个问题的肯定或否定答案。好的。所以你正在尝试计算，

某些东西，它说，你知道，是或否，作为，并给你正确的答案。你输入一些东西，它会返回。你问它一个问题，算法运行，它最终会给你一个肯定或否定的答案。好的。这叫做 NP 类。好的。并且，嗯，

所以这将是所有决策问题。实际上，所有可以在多项式时间内证明的决策问题。我的意思是，如果你有一个答案，你可以在多项式时间内证明这个答案是正确的吗？好的。如果你能做到这一点，那么这个决策问题就被认为属于 NP 类。好的。现在有一个子集，

NP 类，或者正如我们将看到的，我们相信 NP 类中有一个子集，我们会说，好的，这些是决策问题，你不仅可以在多项式时间内证明答案是正确的，而且你可以在多项式时间内找到答案。这叫做 P 类。好的。现在我正在画，我正在画这个，P 是 NP 的一个子集，但这里有一个奇怪的事情，那就是，

你怎么知道一个决策问题，所以如果我们有一个特定的算法，我们可以判断该算法是指数的还是多项式的，或者它是线性的，对吧？但是你怎么知道那个决策问题是指数的、多项式时间的还是线性的呢，对吧？现在，你不能简单地说，哦，好吧，我知道一个算法来解决这个决策问题，它是指数的，因此这个决策问题是指数的。因为你将来可能会发现

发现另一个解决相同决策问题的算法，实际上速度更快，对吧？如果这听起来有点熟悉，那是因为这与我们在前四集中讨论过的认识论相同。如果你有一个算法，你知道它的速度是多少，

但是如果你有一个决策问题，你并不能确定该决策问题的最大速度是多少，因为你不知道将来是否会发现一个算法，使该算法更快。好的。我明白了。好的。

所以一件可能的事情，至少在逻辑上是可能的，那就是没有一个与 NP 类不同的 P 类。所有决策问题实际上都可以在多项式时间内运行，我们只是不知道而已。好的。好吧，没有人真正相信这一点。

好的，那么从理论上讲，这可能是真的。对。但这真的很难相信，对吧？我的意思是，有很多有趣的决策问题，人们一直在研究，而如果你从事计算理论的研究，你正在尝试提出解决这些问题的最快算法，并且

其中一些决策问题真的很难改进，也很难为其找到非指数时间算法。对。所以他们实际上，而这是，我一直认为这非常聪明。他们实际上提出了证据，而不是证明，而是证据，

P 和 NP 不是同一个类。我将尝试简要地向你解释一下，因为我认为这非常酷。好的。所以还有一类算法，它的名字非常奇怪，叫做 NP-hard。它被粗略地定义为至少与 NP 中最难的问题一样难的问题。这听起来可能几乎毫无意义，但我已经完成了，它会有点意义。

所以 NP 类实际上不是 NP 的子集。我在屏幕上画的方式，它部分在 NP 内部，部分在 NP 外部，这是正确的。对，好的。因为它在 NP 之外，这意味着 NP-hard 中有一些问题不是决策问题。事实上，很多搜索问题，你并不是试图用是或否来回答，这是真的吗？但是给我我接下来需要做的最佳事情。那将是不一致的。

考虑一下你正在尝试选择接下来要做什么。如果你问这个问题，这是我接下来要做的最优的事情吗？这是一个决策问题。如果你问我的待办事项列表中，哪个是我接下来应该做的？这是一个搜索问题。好的。所以 NP-hard 包括搜索问题。它不仅仅是决策问题。现在，NP-hard 的子集在 NP 中，那就是

NP 问题中最难的类别。他们已经决定了 NP 问题中最难的类别。他们称之为 NP 完全问题。好的。所以有一些，它们是 NP-hard 的一部分，但它们也是 NP 的一部分。这就是 NP 完全问题。这说得通吗？是的。是的，这说得通。好的。它让我头疼，但它说得通。是的。是的。

所以 NP 完全问题是一类非常特殊的问题。原因是它们是普遍存在的问题。好的，我们谈到了图灵机是如何成为一台通用机器，一台通用计算机的。对。这里是一个类似的概念，普遍性。这里的想法是……

任何属于 NP 类的算法都可以简化为 NP 完全问题。可以将它们重新表述为任何 NP 完全问题。我这么说可能有点奇怪。

这与我在上一集谈到的例子没什么不同，我们谈到了确定性有限自动机与正则表达式的等价性。因此，我们证明了可以进行单向转换，也可以进行反向转换。反向转换，是的。好的，所以可以证明NP中的所有算法都可以转换为NP完全问题。你不能一定能转换回来。

他们真正做的事情，这很巧妙，他们证明了NP问题可以转化为，嗯，基本上是逻辑电路门，对吧？他们，他们，

他们可以证明，哦，每个NP问题，都可以构建一个小型的电子电路来解决它，使用与门和或门以及逻辑。然后使用一个可满足性算法，它说，好吧，有什么方法可以满足这些电路，使它们都为真？这将给你原始NP问题的答案。通过这样做，他们提出了第一个NP完全问题。从那时起，他们就可以使用归约来开始证明其他问题是NP完全的。

如果你要NP完全，事实上，所以基本上如果你有一个NP完全问题，假设你有一个NP完全问题，旅行商问题就是一个NP完全问题的例子。如果你能为它想出一个多项式时间算法，那么NP类中的每一个算法，所有判定问题，

都将成为多项式时间算法。因为你可以做的是，你可以取NP问题，你可以把它转换成旅行商问题，你可以在旅行商问题上运行你的多项式时间算法，得到答案，然后把它转换回NP问题的答案。所以基本上从那时起，每一个NP问题现在都将是一个多项式时间算法，并且将更容易处理。好的。

因为它真的很难相信这是可能的。所以这是作为证据而产生的，即MP类中某些问题将永远难以处理，对吧？没有办法真正使它们的算法成为多项式时间，好吗？你都明白了吗？这有点技术性，这可能是我们在播客中尝试做的最难的事情之一，

有点超过了一点点技术性。这是相当技术性的。

所以，但是NP完全，如果这个的总结是，如果你曾经为任何单个NP完全问题找到一个多项式时间算法，那么你将拥有NP类中绝对每一个判定问题的多项式时间算法，对吧？正因为如此，我们不期望我们能够找到任何NP完全问题的多项式时间算法。

这种……我们现在只是假设我们永远都找不到一个，因为……是的。所以我们最好的理论是P和NP是不同的类，并且有一些问题将永远难以处理。这就是事情与人工智能联系起来的地方。好的。人工智能可能不止一件事，但它主要研究的一件事是如何处理

我们想要解决的问题，它是NP完全的，也就是说，没有办法或NP难，没有办法以易于处理的方式解决它。好的。

好的，所以人工智能是，他们定义了理性，这与我们在前四集中学到的认识论相矛盾，但他们定义它与经济学相同。他们将理性定义为：你试图完成某事，你试图做出决定，并且你想做出最佳决定。好的，你想获得最佳结果。

所以理性是在经济学中试图优化你的利益，对吧？对错或漠不关心，这就是经济学的定义方式。所以人工智能是，鉴于这个问题难以处理，我们能多接近理性结果，最佳结果？

然后你可以使用很多不同的技术来尝试处理一个难以处理的问题。然后它又带我们回到了深蓝，深蓝试图解决许多步数。然后它有一个非常巧妙的棋盘评估算法。所以，不必为了看看谁赢而解决到游戏结束，它有一个非常强大的能力，在这种情况下由程序员手工制作，呃，

强大的能力来预测许多步数，然后说，这一步将导致这种情况，在这种情况下，我可以将棋盘置于这种状态，这将是我的最佳状态，最佳状态。对。

这就是它解决这个问题的方式。这就是它能够下棋比任何人都好的方式，仅仅是试图找到一个最佳解决方案，尽可能接近最佳解决方案，尽可能接近一个已知难以处理的问题的最佳解决方案。对。

所以这实际上就是为什么我发现人工智能非常迷人。机器学习有点不同。它也是人工智能的一部分。它更像是对我们如何想出一个我们不知道如何编程的算法的研究。但是你可以看到那里仍然存在某种关系，对吧？我们试图让计算机为我们不知道如何做的事情找到解决方案，我们无法理想地完成的事情。所以我们想尽可能接近。

今天关于计算理论的最后一个概念是不可判定性的概念。

所以不可判定性。所以有些问题。物理定律根本不允许我们计算答案。所以我们不是在谈论。所以难以处理的是我们知道如何得到正确的答案，但是没有计算机能够建造得足够快以让我们得到我们需要的答案。好的。不可判定性是没有办法计算它。好的。我记得，嗯，嗯，嗯，在工作中有一个朋友，嗯，

问什么是不确定的？什么是不可能计算的？他无法想象那会是什么。生活中实际上有很多事情是无法计算的。现在，我们有史以来第一个不可计算性的例子来自艾伦·图灵，并且

它被称为停机问题。所以基本上想象一下你有一个算法，你想计算一个答案，你开始运行算法，它没有结束，对吧？它只是，它一直在运行，它一直在运行，它一直在运行。你可能不知道算法是否会永远运行，或者它是否需要运行数十亿年才能运行，对吧？

如果我们有一种方法可以获取该算法，将其输入到另一个算法中，然后说，好的，这个算法最终会完成并结束并给我一个答案吗，它只是需要很长时间吗？对。或者这个算法实际上只是在一个无限循环中，对吧？

所以，图灵证明没有通用的算法可以解决停机问题，因此它被称为不可判定。好的。而且

这实际上很有趣。有可能确定对某些个别情况的答案。所以，这个，这个，“通用”这个词在这里很重要。没有通用的算法可以解决这个问题，但是使用创造力，你也许能够想出一些解决它的方法。所以，比如说，算法只是一个无限循环，对吧？它只是说，你知道，第10行，转到第10行之类的东西。那么，

你可以想出一个知道如何解决那个停机问题的算法，对吧？一个具体的例子。好吧，所以实际上有一些具体的，有一些个别情况可能是可以解决的，但是没有通用的算法可以解决每一个情况。图灵能够证明这一点。

然后从那里，他们所做的是使用归约来证明，好的，这个问题，如果你能，他们所做的是从假设开始，我们将采取一个问题，然后他们会说，好的，我有这个问题。所以我在这里使用的例子是，想象一下你有一个图灵机上的程序，你想知道它是否也能在有限自动机上运行。

好的。这实际上很有用。这个，这个程序，是否可以将其移动到有限自动机上，或者它是否使用了某些东西，使其无法在有限自动机上运行它？你会做的是，你会从假设开始，好的，

这个，你有一个可以解决这个问题的算法。然后你证明，如果你有那个算法，你就可以解决停机问题。好吧，我们知道你无法解决停机问题，因此通过反证法，你已经证明了那个新问题也是不可判定的。好的。所以计算理论中他们做的另一件事，除了研究难处理性之外，就是不可判定性。这是一个根本不可能得到答案的算法吗？对。

现在，是的，不，不，让我在这里让你大吃一惊一会儿，因为我一直忽略了量子计算机。好的。

我认为我们在这一集开始时就决定要这样做一段时间。所以量子计算机与图灵机并不一定有很大的不同。所以戴维·杜伊奇的工作使他成名，他证明了量子计算机是图灵完备的，它可以运行图灵机可以运行的任何程序。

我还告诉你，量子计算机可以模拟模拟，而

图灵机必须始终进行数字运算，但它可以达到我们想要的任何逼近程度，对吧？所以这是两者之间的另一个区别。两者之间还有另一个非常大的区别。量子计算机，他们提出了一种称为肖尔算法的算法。我想我以前跟你说过这个。这简直令人难以置信。他们有一个可以解决问题的算法

试图找到……所以方法……

安全工作和密码学工作的方式是，他们会取非常大的素数并将它们相乘。然后他们将它用作密钥，作为秘密密钥，对吧？然后他们用它来加密东西，如果你，当你拥有那个秘密时，你知道，你拥有那个公钥。如果你能取那个数字并将其简化为其秘密

原始素数，那么你就可以破解密码学的代码并阅读秘密消息。对。但是这个问题现在已知属于NP类。所以现在不可能创建一个易于处理的算法来解决这个问题。好的。它不是NP完全的。然而，它是NP，而不是NP完全的。

而量子计算机使用肖尔算法可以解决这个问题，即使它需要指数数量的计算。

所以量子计算机，太糟糕了，它不是NP完全问题，因为那样它就会把NP类中的所有东西都变成等同于P类。但不幸的是，它只是一个非常具体的问题，素数。但它可以在多项式时间内解决那个指数时间问题。而杜伊奇……

它能够做到这一点的原因是因为它是在多个世界中解决问题的。它们有无限多个。因此，有足够的证据

能够快速地在多项式时间内进行计算。关于肖尔算法有趣的一点是，现在我们无法构建量子计算机。我们不知道如何设计一个，但他们做得越来越好。我们最终将能够做到这一点。他们实际上可以构建量子计算机。它们只是太小了，对吧？此时，它们的量子比特数量不足以使用，但它们正在接近，一旦它们能够做到足够数量的量子比特，使用当前RSA加密的所有东西都被破解了，并且它们

从某种意义上说，这意味着它已经被破解了。所以，如果你是俄罗斯人，你已经在收集所有美国秘密信息，并将它们存储在计算机上，某处的计算机上，你正在等待量子计算机的建造。而且，

然后你，一旦它建成，你就运行肖尔算法，你就读取所有内容。所以在某种非常真实的意义上，我们当前的所有加密已经被破解了。这只是时间问题，因为它都可以被读取。因为量子计算机在某种程度上能够在这种特定情况下，在多项式时间内运行指数时间算法。好的，我想它又让我头疼了。是的。

他们可以用量子计算机做的另一件事是，他们可以对任何指数时间算法进行二次加速，二次不是指数。所以这不是，我的意思是，太糟糕了。我无法进行指数加速，因为那真的会是令人惊奇的事情，但他们可以对任何指数时间算法进行二次加速，这意味着我们将能够比以前更进一步地运行所有指数时间算法。所以用国际象棋的比喻来说，也许我们将能够提前看八次，

现在移动或类似的东西。对。所以它将非常普遍地有用，但它实际上不会解决大多数问题的难处理性问题。我们下次谈论什么？下次我们将讨论图灵原理。我简要地提到了这一点，但我希望更详细地讨论一下，

它的含义及其哲学含义是什么。我在推特上有一个朋友一直在和我讨论这个问题，我答应他我会给他一个更好的答案。他是一个正在研究人工通用智能的人，他认为大脑正在做一些无法计算的事情来实现人工通用智能。

在这些时间中，你将专门做一个关于这个的剧集，并谈论罗杰·彭罗斯，他也相信这一点。所以我对他说，你知道，当然，我不确定你对还是错，但是你假设这一点会有影响，我认为你还没有接受。他说，真的吗？那些是什么？他非常感兴趣。我的意思是，大多数人都会对自己的想法进行非常强烈的辩护。这个人很棒。他想要批评。

对。不幸的是，这不是我通过推特可以解释的事情。所以我答应他我会在未来做，呃，你知道，一篇博客文章或，你知道，一个播客。我们将讨论，嗯，

图灵原理，这就是为什么它是我们最好的理论的原因。这就是为什么我相信人工通用智能可以在今天的计算机、图灵机上完成，并且它不需要一些新的不可计算的物理定律，如果这说得通的话。好的，那应该是一次引人入胜的谈话。我会准备好和你争论。好的。我在开玩笑。我不知道我是否会。好的。

好的。谢谢你，卡米尔。