Episode 9: Introduction to Computational Theory
47:50 Share

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

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

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

谢谢。好了，欢迎收听《万事通理论》播客。卡梅奥，你好吗？非常好。布鲁斯，你呢？很好。所以我们谈到了计算理论。所以我提前快速准备了一些关于计算理论的内容，这实际上是我最喜欢的主题之一。它可能听起来很枯燥。我会努力证明它并不枯燥。

它不是枯燥的。计算理论是计算机科学中的那门课。我年轻的时候是计算机科学专业。我现在正在攻读计算机科学硕士学位，但我多年前获得了学士学位。而计算理论就是他们让你学习的那门课

你根本不知道为什么要学习它。它是什么，他们为什么要让我学习这个？它与编程无关。据你所知，它与软件没有任何关系。他们让你学习它，而且它非常枯燥。它就像一门数学课，你必须做证明，这就像，你知道，每个学生都讨厌做证明。你从课堂上出来，你活下来了，然后你说，伙计，我很高兴我完成了这门课。这是有史以来最糟糕的科目。然后你继续你的生活，再也不会想它了。

你也不会再用它了。我当时也是这么想的。我当时也是这么认为的。当我阅读戴维·杜伊奇的书时，他将计算理论列为他的四大支柱之一，即我们拥有的四个最重要的科学理论之一。首先，这让我很惊讶，因为我从未想过计算理论是一个科学理论。我认为它是数学。大多数人都会这么认为。这就是它在学校的教学方式。

所以这是第一点。我会解释为什么他说它实际上是一个科学理论。它实际上介于科学理论和数学之间。它是连接数学和科学的科学理论。

物理学在一起，这才是它真正的样子。好吧。但是，大多数教授它的人都不知道这一点。所以他们不知道如何向学生解释这一点，以及如何展示它实际上是一个多么有趣的主题。他们把它弄得很无聊。这可能是学校课程中一个更深层次的问题，

低年级课程是由宁愿教授其他课程的老师教授的，所以这门课并不那么有趣。而且学生太多了。这是一个巨大的班级，因为每个人都必须学习这门课，而且人数太多了。它在某个半礼堂里。杜伊奇解释了它真正的含义，它是一个非常有趣的主题。

它真的开始引起我的兴趣。在四大支柱中，这是最引起我兴趣的一个。所以四大支柱是多世界量子物理学、计算理论、自然选择理论，实际上是新达尔文主义，有点像道金斯的版本。

对。这是最成熟的版本。还有波普尔的认识论，批判理性主义。大多数接触四大支柱的人都会接触到批判理性主义。我也喜欢批判理性主义。这就是我们前四期播客的内容。对。

但我最喜欢的还是计算理论。这是我……虽然这是一个很难的领域。所以，你知道，我更像是一个业余爱好者，但正是我对计算理论的兴趣让我重返学校攻读硕士学位。

哦，真的吗？是的。我最期待的一门课（直到他们把它变得有点太难了）是研究生算法，它是……你知道，它是计算理论的研究，这非常有趣，算法，它是计算理论的研究。而人工智能，正如你所知，我正在学习人工智能和机器学习。它们与计算理论有着特殊的关系。事实上，它们几乎就像

计算理论的一个分支。除了我，我不知道是否有人会相信这一点，但在我看来，它们就像计算理论的一个分支。它们与计算理论有着非常深厚的关系。所以，我学习人工智能和机器学习并非偶然。正因为我对计算理论的兴趣，我才选择了这个作为我的专业。

我会在一小时内给你讲一个学期的内容，并向你解释他们在课堂上教你的所有内容，但你不需要做任何证明，也不需要参加任何考试。而且我会让它不那么枯燥。好的。所以我这里有一个例子，对于那些……嗯……

如果你在 YouTube 上观看这个视频，你实际上可以看到我向卡梅奥展示的内容，但你不需要这样做。我会解释一下，这样你就可以在播客中收听。不过，这里有一个例子，叫做有限自动机或自动机，在这种情况下，只有一个。它就像……你知道你走到那些小风格的地方，然后你投入硬币，它就会让你通过，就像……你知道，在迪斯尼乐园，我不认为迪斯尼乐园有硬币，但是

类似的东西。对。当然。好的。这就是它。好的。这个，这个，你知道，你已经……它，它，它是锁定的。你按下它。它只是回到锁定状态。因为你无法通过。你投入一枚硬币。它就解锁了。

你试图投入另一枚硬币，但这没有任何作用。它已经解锁了。然后你穿过它，然后它又回到锁定状态。好的。对。好的。所以，我不记得我从哪里得到这个例子的。我认为它来自 Sipser，迈克尔·西普瑟是编写计算理论中最著名书籍的人。但我无法在他的书中找到它来感谢他。我可能只是在互联网上找到了一个著名的例子。

但这是一个有限自动机的例子。你可能不会认为这样的门是一台计算机，对吧？它显然是一个物理物体。但计算机是物理物体，对吧？

好的。你可以制作一个通用的有限自动机计算机，然后将其插入这样的门中，它就会工作。但在这种情况下，计算机本身就是物理物体。这比你想象的更常见，对吧？因为我要解释的一件事是，一切都是计算。所以一切都是计算机。好的。但是

但是有限自动机，它使用这样的状态和转换工作，它只能执行某些类型的计算。有很多类型的计算它无法执行。

显然这里没有像普通计算机那样的内存。它缺少执行许多你可能想要执行的不同类型计算所需的东西。所以有限自动机是一台计算机，但它在可以执行的计算类型方面受到限制。好的。明白了吗？是的。是的，它本质上有一个单一的二进制过程。是的。是的。好的。

好的，所以任何你可以用状态和转换编写的程序，那将是一个有限自动机。你可以在有限自动机计算机上运行它。请记住，这些是理论计算机。我怀疑这不会有用到有人会在现实生活中构建一个有限自动机计算机的地步。在计算理论中，我们并不那么担心

有人会在现实生活中建造它吗？我们试图研究它的理论，对吧？所以这是一个重要的概念。好的。现在你可能熟悉正则表达式，也许是从

你的工作。事实证明，正则表达式是一个有限自动机。它们是一样的。正则表达式可以执行的任何计算都是有限自动机可以执行的计算集，反之亦然。现在，这可能根本不明显，因为如果你熟悉正则表达式，你知道它可以执行某些非常有用的计算类型，但是

它们是有限的。你不会去编程，你知道，你的整个应用程序只在正则表达式中。那是不可能的。对。所以，

现在，我们怎么知道正则表达式等同于有限自动机呢？好吧，这是一个有趣的问题。但在讨论这个问题之前，让我先指出一些其他事情。有限自动机有一个概率版本，称为马尔可夫链，你可以在其中说，如果你处于这种状态，那么你将转换到这种状态的概率是多少，或者你将尝试转换到这种状态的概率是多少。有一个非确定性有限自动机，它是

这个名字具有误导性。它实际上只是意味着你可以并行处于许多状态，这使得它在理论上至少在工作方式上更高效。

在程序中移动。然而，非确定性有限自动机运行的程序类别与确定性有限自动机完全相同。所以即使它在理论上可能更快，它也不会更强大。它不能表达有限自动机无法表达的算法或程序。你会认为它可以，因为它可以处于多个状态，但它不能。那么，我们怎么知道正则表达式与有限自动机相同呢？

好吧，这就是如何证明它，好的？所以假设我们有，所以我们有这个类，确定性有限自动机。我们将使用确定性，因为它更容易证明。但实际上，由于 NFA 和 DFA 等效，这个证明对于 NFA 也同样有效，好的？然后我们有这个类，叫做正则表达式。所以我们想做的是

并且，如果你是正在学习这门课，他们实际上会带你完成实际的证明，我不会这样做。但他们会向你展示，将任何有限自动机转换成正则表达式是可能的。所以没有你不能转换成正则表达式的有限自动机。

好的，明白了吗？所以他们会首先创建这个证明。是的，是的，绝对的。好的，然后他们会做相反的证明，他们会说，现在我们将证明每个正则表达式都可以转换成有限自动机。所以他们会完成这个证明。当你完成了证明的两面时，你就证明了这两者是等效的。你能看出情况是这样的吗？

是的，绝对的。是的。是的。好的。所以这是计算理论的一个重要部分，即证明，他们试图证明这个等同于那个，或者这个不等同于那个。诸如此类的事情。好的。现在还有另一种类型的计算机，叫做下推自动机 PDA。好的。不要与公开表达爱意混淆。不，不。你不会想把这两件事混淆的。是的。

所以唯一的区别是，它与有限自动机相同，但它有内存，它有一个堆栈连接到它。你可以将数据压入和弹出堆栈。好的。然后你可以将其用作转换的一部分。所以内存的添加确实使它成为一种更强大的计算机。现在请记住，就“强大”而言，我的意思是它可以表达更多类型的程序、更多类型的算法。好的。

我们习惯于认为计算机的强大意味着速度更快。这是一种合法的思考方式，但这不是我们在这里讨论的内容。这是一个更基本的强大概念。好的。它实际上是你是否可以在计算机上表达程序。当然。所以，嗯……

现在，下推自动机等同于所谓的上下文无关文法。所以我不会深入讨论这个问题，但概念完全相同。你可以证明你可以将一个计算成另一个，然后再转换回来。好的。那么，你可以在 PDA 上运行在 FA 上无法运行的程序吗？好吧，我已经告诉你答案是肯定的，但你会如何证明呢？好吧，

好吧，这实际上有点复杂。所以首先我们要证明 DFA 上的所有程序都可以在 PDA 上运行。好的。这并不难证明。基本上，证明包括这一点，这个第一个转换 DFA 到 PDA，你证明它的方法是说，如果你不使用 PDA 上的堆栈，它与 DFA 完全相同，因为这就是它的设计方式。好的。

好的。因此，我知道每个 DFA 也是一个 PDA，一个 PDA 必须是，必须是，不能是 DFA 的子集。明白了吗？是的。现在，

现在，第二种方法，我们试图不证明它们是等效的，而是证明它们不是等效的。所以我们试图证明你不能将每个 PDA 转换成 DFA。好吧，这更难证明，好的，因为你现在试图证明一个否定，好的？所以他们必须在这方面变得聪明，关于他们将如何进行这个证明。他们所做的是找到一个程序，可以证明有限自动机

自动机无法运行，但他们可以证明 PDA 会运行 PDA。证明它在 PDA 上运行很容易。你只需展示算法即可。证明它不会在 FA 上运行则比较困难，我不会深入讨论这个证明，但他们能够证明这个程序无法在 FA 上运行，但这是它的 PDA 版本。因此，这表明

DFA 是 PDA 的子集。所以 PDA 比 DFA 更强大，因为……

因为它可以运行 DFA 可以运行的每个程序，或者任何有限自动机可以运行的程序，而不仅仅是确定性程序。但它还可以运行 DFA 无法运行的程序。好的，所以它是一台更强大的计算机。到目前为止，你都理解了吗？我完全理解，是的。好的。所以我们因此知道 PDA 比 DFA 更强大。所以现在有……这引发了一个问题。

是否存在最强大的计算机器，或者是否存在无限多个越来越强大的计算机器？我们将不断发现新的、更强大的计算机器。还是它达到了极限？是否存在某种类型的机器是最强大的？

好的。请记住，我们不是在谈论运行速度更快，拥有更多内存。这是不同的强大概念。我们谈论的是表达算法或程序的能力。好的。所以随便猜猜吧。你认为这两个答案中哪个是正确的？是否存在最强大的一个，或者是否存在无限多个越来越强大的计算机器？好吧，

我认为可能存在，但我也有很多理论知识说不存在。所以这不是一个答案，但是……没关系。

所以这是一个非常重要的科学和哲学问题。好的。所以我们将尝试根据我们今天所知来回答这个问题，通过提出我们对该主题的最佳理论。对。好的。

所以有一个人叫艾伦·图灵。你可能熟悉艾伦·图灵。你应该看过《模仿游戏》，我猜。当然，当然，当然。是的。一部很棒的电影。任何没有看过的人，都去看吧。这部电影让他在门外汉中出名了。但我们之前就学习过艾伦·图灵，

在我还在……你知道，计算机科学的时候，自从他活着的时候，他就已经在计算机科学界因计算理论而闻名。当然。他至少被认为是计算的教父之一。

他被认为是计算理论的创造者。哦，好的。是的。正如我们将看到的，他和阿隆佐·丘奇共享这一荣誉，但图灵在这方面可能比丘奇走得更远。这就是为什么他被认为是计算理论之父的原因。好的。

所以丘奇和图灵大约生活在同一时期。他们是同时代人。他们都在大约同一时间提出了假设的计算机器。好的。所以很明显，艾伦·图灵提出的计算机器被称为图灵机。这是两者中更著名的一种。它基本上是一个可以从磁带上读取和写入的机器。

所以你可以从磁带上读取指令，或者你可以向磁带写入内容。所以他开始研究你可以在这个机器上执行哪些类别的计算？你知道，它是否比下推自动机更强大？诸如此类的事情。他开始研究很多这些东西，丘奇也出现了，他的“机器”更像是一种语法。所以它不是一个真正的……图灵实际上将其设想为一台物理机器。

从未真正建造过。我的意思是，它今天已经被建造出来了，但这更像是一种好奇心。它从未打算被建造，对吧？试图用一个读取和写入的磁带制作一台计算机可能不是制作计算机最方便的方法，但它在概念上很容易理解。当你试图向学生教授这一点时，这很重要，对吧？所以丘奇的机器很难理解。它是你使用的语法，但它使用语法进行计算。

因此也可以被认为是一种机器。所以丘奇机和图灵机大约在同一时间出现。图灵证明这两台机器完全等效。

好的。他提出了证明，就像我刚才向你展示的那样，你可以将一个转换成另一个。然后另一个转换成它，证明了这些是等效的机器。它们完全不同。它们彼此如此不同。那么，为什么这两台机器最终完全等效呢？这似乎是一个非常大的巧合。好的。就像，哇，我们有这两个聪明的家伙提出了计算机器，而且它们是

它们提出了完全不同的机器，但不知何故，它们完全等效。它们可以运行彼此完全相同的算法，就是这样，对吧？所以就像，哇，这是一个重大的巧合。还是巧合？好的，让我们谈谈如何……

如何发生这种情况。好的，那么两台独立创建的机器，两台独立创建的机器如何才能等效呢？那么，如果物理定律允许的计算能力是有限的呢？好的，那么图灵机和丘奇机等效就不是巧合了。它们碰巧达到了允许的最大限度。好的，并且因此

如果这是真的，那么我们创建的每一台机器都将等效于图灵机。我们将能够证明它等效于图灵机。所以他们试图提出其他更强大的计算机器，他们今天仍在研究这个问题，对吧？

我最喜欢的一种是带有二维纸张的图灵机。所以，与其只有一个磁带，你实际上可以在两个维度上移动，并且可以读取和写入任何……你知道，纸张上的任何地方。好的。你知道，你会真的认为这会使它比图灵机更强大，但事实并非如此。好的。你总是可以提出一个证明，证明这与图灵机完全等效，而图灵机与它完全等效。好的。事实上，自发明以来，每一台计算机都已被证明等效于图灵机。所以，好的。那么为什么是这样呢？所以让我们，让我们先谈谈现代计算机，因为这甚至可能有点令人惊讶，图灵机，它真的等效于现代计算机吗？还是现代计算机更强大？

好吧，现代计算机实际上非常像图灵机。所以你有内存，你可以访问内存中的任何位置，而不是必须在磁带上前后移动。但内存是一系列单元格，你将值放入其中，从零开始，一直到最大数字。它与磁带完全相同，对吧？对。所以现代计算机比图灵机快，你知道，

显然，按照今天的标准，图灵机将非常慢，因为它可以访问任何地方。我们已经把它放入硅中，它非常快，因为它非常小等等。但在现代计算机与图灵机可以表达哪些算法方面，实际上，图灵机比现代计算机更强大，这

这可能会让你感到惊讶。哦，是的。有趣。不，它们是……它们在说图灵机在技术上作弊时，因为它只是……它不是一台真正的计算机，它不是……不是一台物理计算机。它有一个物理的，它有无限的内存。没有现代计算机可以拥有无限的内存。对。所以这是两者之间的实际区别。除此之外，它们是一样的。对。所以，嗯……

而且我们假设一台具有无限内存的机器是有原因的。事实是，区别并不大，因为你总是可以说，如果我的程序需要更多内存，我将继续购买更多物理内存和 Veticomtube，它可以处理更多物理内存。

因此，基于这一点，我们通常将现代计算机和图灵机视为基本等效的。即使在理论上，具有无限内存的图灵机将始终能够做现代计算机无法做的事情，直到他们能够为其获得更多内存。对，对。好的。

那么，我们能否证明图灵机是最强大的计算机呢？好的。到目前为止，我们已经通过证明完成了一切。我们证明了有限自动机等效于下推自动机，诸如此类的事情。这实际上被认为是数学的一个分支，其中一切都是通过证明完成的。

所以他们并没有准备好这样一个事实，即似乎没有证明图灵机是最强大的计算机。哦。

而且没有人能够提出这样的证明。事实上，我相当怀疑你能提出这样的证明，我会尝试解释原因。那么，你将如何证明永远不可能有更强大的计算机呢？我认为你做不到，对吧？总是有可能，我想，我们会想出一些我们还没有想出的计算机，它可以

可以做当前计算机无法做的事情。就像我说的，量子计算机实际上略微符合这种类型的计算机。它可以做一些图灵机无法做的事情。区别似乎在于，它可以更快地做一些事情，但请记住我们不计算速度。所以它可以表达模拟而不是数字，这使得它略有不同，但不是以一种……我的意思是，我不知道我们是否知道具体的

你不能在普通的图灵机上以你想要的任何级别进行近似的算法。所以它不像你想象的那么例外，对吧？它仍然处理非常接近同一类算法。好的。所以，嗯……量子计算机真正让大家兴奋的是

是肖尔算法，这是一种可以破解任何加密，任何 RSA 类型加密的算法。实际上，我应该在这里小心。有一些类型的加密它无法破解，例如常规的 pad 加密等等。但这些并不那么有用。所以我们广泛使用来保护您的信用卡或保护……你知道，

政府机密或类似的东西，它可以破解那种类型的加密。所以德意志指出，由于肖尔算法已经存在，我们只是还没有实例化一台可以运行它的计算机，从某种意义上说，所有加密已经被破解了。

所以，如果你像是俄罗斯人，你已经存储了你可以从美国获得的每一个加密的秘密。然后你就在等待量子计算机的发明，等待它的工程化。我明白了。然后你就把它们都读出来。对。所以在非常真实的意义上，所有加密已经被破解了。人们没有意识到这一点，但这是事实。好的。因为这只是时间问题，我们实际上会设计出一台量子计算计算机。它在一个单独的上下文中。

播客我会谈论它是如何工作的，但量子计算机能做的事情真的很奇怪，因为它使用了，你知道的，量子力学。由于量子力学是基于叠加和纠缠等等，它可以进行比宇宙中原子数量更大的计算。

哦，好的。原因是它使用了多重宇宙。所以它是在多重宇宙中进行计算，而不是在一个单一宇宙中。当然。所以这就是为什么它能够比任何其他，你知道的，普通的图灵机工作得更快。好的。所以我们现在已经证明了比图灵机更强大的机器的理论存在。所以我们并不是不能设想一个，

一台比图灵机更强大的计算机。确实存在所谓的超图灵机，但它们违反了物理定律。它们在现实生活中无法建造。对。好的。而这，这也是我怀疑你将来会看到某种更强大的计算机类型的原因之一，即使我们无法证明它。

是因为我们现在真正谈论的是物理定律。我们谈论的是物理定律允许什么？好的。所以，你知道，也许未来的物理理论可能会允许超图灵机，但我认为在任何现有的物理理论下都不会发生，对吧？所以它是，

谁知道呢？我的意思是，当我们研究量子力学时，我必须找到这段话，但罗杰·彭罗斯引用大卫·德意志的话说，某些类型的预言机他们也许能够建造，这将因此成为一台超图灵机计算机。但我们目前不知道有任何方法可以做到这一点。所以他们最终放弃了证明，他们称之为，他们发明了一些叫做丘奇-图灵论题的东西，因为它不是一个证明。

好的。丘奇-图灵论题后来被修改为丘奇-图灵-德意志论题，以考虑量子计算。但我通常会省略这个论题的德意志部分，因为无论如何快速解释量子计算机都太难了。所以我们只把它称为丘奇-图灵论题。好的。而德意志指出，这个论题是……

实际上是一个完整的科学理论。好的，现在人们不这么认为。你几乎可以把它看作是一个丑闻，我们有一个关于计算的非常重要的原理，叫做丘奇-图灵论题。它是所有计算理论的基础，但我们没有它的证明。好吧，德意志指出，实际上，这是一个科学理论。由于我们在之前的播客中讨论过的原因，任何科学理论都没有证明。

事实上，这真的是物理学的一个分支。所以当然没有它的证明，对吧？好的，所以我们没有丘奇-图灵论题的证明不一定是件大事。一旦你开始把它看作是最好的理论，你知道，它是我们最好的理论，

计算理论，它是我们最好的科学理论，并开始把它看作是一个科学理论，那么它就不足为奇了，对吧？它就像任何其他科学理论一样。它是我们所能推测和提出的最好的理论，我们不知道有任何反例。而且没有竞争理论。那里没有我们仍在研究的替代计算理论，它是一个强大的竞争对手。它没有竞争对手。它是唯一存在的计算理论，对吧？对。

对。所以正因为如此，这使得它很特别。这就是我们在前四个播客中讨论的内容。

当你没有竞争理论时，那就是你最好的理论。你应该接受它为真理。暂定地，是的，但你应该接受它为真理，并且你应该思考它的含义是什么。好的。所以我在这里声称它是丘奇-图灵论题。当你把它看作一个科学理论时，它是迄今为止创建的最好的单一测试理论。现在有些人肯定会就此与我争论，而且我

事实上，你通常会听到的是，量子理论是有史以来最好的单一测试理论，我们没有一个反例。好的。就像即使是爱因斯坦的广义相对论，我们也知道它失效的情况，比如在黑洞中。对。它不起作用的地方。量子理论，我们现在不知道有任何例外。而且，

它可以被测试到，你知道，即使它是一个概率论，你也可以把它测试到小数点后第10位或类似的东西，对吧？我的意思是，它是一个超级精确的理论，你知道，比我们拥有的任何其他理论都要精确得多，对吧？所以很多人会说量子理论是最好的单一测试理论。好吧，我要指出的是，每一次对量子物理学的测试也是对丘奇-图灵-德意志论题的测试。因此……

因此，根据定义，丘奇-图灵论题是我们有史以来最好的单一测试理论。事实上，我要更进一步。我不会在这个播客中深入讨论，但是，所有的科学实际上都是基于丘奇-图灵论题，在我看来。好的。这意味着每一个科学理论也是对丘奇-图灵论题的检验。因此，它不可能不是科学中最好的单一测试理论

在科学中。这些是你说的大胆的话。是的，它们是大胆的话。我必须在未来的播客中证明它们。好的。而且你知道吗，作为一个，作为一个概述，考虑一下数学和科学是如此紧密地联系在一起的事实。对。我的意思是，很难想象没有数学的物理学。

你不会认真对待一个没有数学基础的物理理论。不，绝对不会。但是数学是图灵兼容的。所以它是一个基于数学的理论这一事实使它成为一个计算理论，因此与计算理论相关。你是否可以计算它仍然由计算理论决定。所以每一个至少基于数学的理论

也是对丘奇-图灵论题的检验。这部分应该很明显。对。我可能会受到一些反对的地方是在那些不是基于数学的理论上。我认为它们仍然是基于算法的，你甚至无法向人类解释某些东西，除非把它转换成等同于算法的东西，在那里他们理解这意味着这意味着。所以我认为所有科学理论，事实上，所有解释，所有理性，都根植于丘奇-图灵论题。对。

好的，那么丘奇-图灵论题是什么？你会听到它以不同的方式陈述。我将以一种正确的方式陈述它，但这可能不是大多数人认为的方式。所以它的意思是，不可能提出任何类型的计算机器，它可以执行一台普通的图灵机无法执行的逻辑程序。好的，这将是通俗地解释丘奇-图灵论题的一种方式。

好的。这意味着图灵机及其等价物是最强大的可能的计算机器类型。而且没有我们还不知道的更强大的机器。好的。这就是丘奇-图灵论题，这是一个科学理论。它不是一个数学证明，但这是我们目前关于计算的最佳理论。这说得通吗？是的，说得通。很好。那么图灵原理是什么呢？

罗杰·彭罗斯是创造了图灵原理这个术语的人。它实际上与丘奇-图灵论题相同。然而，丘奇和图灵对此有不同的看法。所以丘奇对此有点害羞。所以丘奇把丘奇-图灵论题简单地理解为存在的每一个算法都可以在图灵机上运行，这使得某些东西是非算法的可能性仍然存在。

好的。图灵不能，没有，没有认为存在非算法的东西，对吧？这正是我刚才，

刚才声称的。对。当然，如果我说，你知道，给我一个非算法的东西的例子，你知道，你可能会想出一些非常模糊的东西。我们不太了解，然后我无法给你一个算法，但这并不意味着算法不存在。对。事实是，我们甚至不清楚我们所说的非算法是什么意思。所以图灵把它推到了它的逻辑结论。他指出，实际上，一切都是算法的。因此，

图灵原理等同于丘奇-图灵论题。图灵原理是说，自然界中的所有东西都可以在图灵机上模拟。因为它只是物理定律，对吧？如果物理定律允许某种东西，

让我们在物理上做一些你无法在图灵机上模拟的事情，那么我们将用这个物理过程建造一台计算机，然后我们将拥有一台能够做到这一点的计算机。对。好的。这就是一切都是计算的意义。一切等同于计算。所以采取这样的立场，存在比图灵机更强大的计算机，我们只是还没有发现它们。

你可以采取这个立场。没有什么能阻止一个人采取这个立场。就我所知，这是一个正确的立场，对吧？但这将违反波普尔的认识论，原因是因为我们现在正在比较一个解释，我们最好的理论，丘奇-图灵论题，和一个非解释。这句话，存在比图灵机更强大的计算机，我们只是还没有发现它们，这不是一个解释。它只是破坏了一个好的解释。对。

一个好的解释版本将是，这是一台比图灵机更强大的计算机，这就是它的工作方式。对吧？这将是一个竞争性的解释。我们没有这样的解释。好的？

所以就是这样。这是我的第一部分。我必须在未来的播客中更深入地探讨你可以用计算理论做什么。然后最终，计算理论的哲学含义是什么？不过，为了可能举一个这样的例子，因为我认为这很有趣。我正在和一位神经科学家交谈。她拥有神经科学博士学位。而且

我向她解释我对人工通用智能的兴趣。她大声地想知道，实际上是否有可能建造一个人工通用智能？我说，是的，可以。她说，你不可能知道。我说，你说得对，我不能知道。但是，是的，是的，这是可以做到的。

她说，好吧，你怎么知道？我说，因为大脑是一台计算机。她说，好吧，不，我不知道我是否认同这个类比。我知道许多认同大脑是计算机类比的神经科学家，但也有一些不认同的。我说，不，这不是一个类比。大脑是一台计算机。好的。她那时是不是对你感到沮丧？是的。

好的，但我真正想说的是，我想说的是大脑遵循物理过程。物理过程可以用物理定律来描述。物理定律可以在图灵机上计算。对。所有这些都是没有争议的理论，对吧？我的意思是，它们实际上只是，对此没有已知的例外，对吧？所以当人们试图说你不能在计算机上构建 AGI 时，对吧？

他们想象的，无论他们是否意识到，他们想象的是大脑具有违反我们目前对物理定律理解的生物过程。有趣。好的。而且你知道吗？就我所知，这是真的，对吧？我们总是暂时持有我们的理论，暂时持有我们最好的理论，但我还没有认真对待这个观点，因为

因为没有解释。我没有可以指出的竞争理论。当有人真正创造出那个竞争理论时，我会去看它。然后你会考虑它。对。对。但在那之前，有无限数量的这种非解释性

解释性理论。我没有时间去认真研究它们。我甚至不知道我该如何认真地去研究它，对吧？所以，当然他们没有意识到他们在说些什么。有些人确实意识到了这一点。我认为大多数说这些话的人都不知道他们在声称大脑正在做一些违反我们目前对物理定律理解的事情。罗杰·彭罗斯是一个非常有趣的例外

我刚刚听了他的一次采访。事实上，我会让你听同样的采访，然后我们会做一个播客讨论他的观点。好的。但是，呃，对。我之前提到过他。他是史蒂芬·霍金的老师。对。他非常聪明，也是我最喜欢的作者之一，但我不同意他的所有结论。而且，而且，

在采访中，他直接说出来了。他说，不，我比人们想象的要走得更远。我不是说大脑是一个量子计算过程，因为量子计算过程仍然等同于图灵机。他理解这一点，而大多数人都不理解。对。他说，不，我认为量子物理学中有一个我们还不了解的不可计算的过程。对。

好的。而且我们最终会得到一个新的量子物理学理论。所以他完全抛弃了现有的理论。这是人们忽略的一点。最终会有一种新的量子物理学理论，其中包含不可计算的元素，而这是我如果，如果我能让他接受采访，我会问他的问题，我们甚至该如何理解它是什么？你不能用数学来描述它。

我的意思是，对于它在做什么，我们永远都会不透明。我们试图拒绝我们无法用数学描述的东西。这是正确的。我们这样做是对的。这是波普尔认识论中出现的东西。我们有理由拒绝那些……

根据定义，我们认为是无法解释的东西，对吧？我们应该总是寻求解释。好吧，这是，你知道，我认为我们在上一集简短地谈到了那些对量子物理学应用某种形而上学，嗯，

几乎是宗教元素的人。我认为这是整个量子物理学理论中吸引他们的一部分。他们感觉到了这一点，就像，这是我们无法描述的东西的答案。

这很有趣。而且你知道吗？而这是，我们需要做一个播客，事实上，我正在努力最终做一个关于多世界量子物理学的播客。但是人们为什么在量子物理学中隐藏神秘主义的原因是，一旦你声称没有解释，你就可以在其中隐藏任何东西。好的。这是一个真理。对。好的。

从哥本哈根对量子物理学的解释成为最流行的解释的那一刻起，它今天可能不是最流行的，但它在很长一段时间内是最流行的。它采取的立场是对量子物理学某些方面没有解释。假设没有解释，甚至没有理由去寻找解释的结果是，你可以隐藏任何东西。

任何东西。哦，有趣。好的。这就是为什么在多世界解释接管之前，它正在慢慢地接管，但在多世界解释接管之前，总会有想要在量子物理学中隐藏神秘主义的人，因为它没有解释。对。你可以去找你的物理老师，他们会告诉你没有解释。对。

对。别担心。对。他们说这是一个无效的问题。甚至不要问。好的。这就是当今世界上的大多数物理老师、教授会告诉你的。而他们告诉你这一点的危险在于

他们打开了通往任何事物的大门。你知道，数学中也有一个完全类似的原理，我经常会向你展示它，但是有一个证明，如果你能证明一个数学系统允许任何一个矛盾，那么它就允许每一个矛盾。嗯哼。

好的。所以它基本上取消了整个数学系统。所以如果你允许一个矛盾，那么你可以证明任何事情都是真的。在那段时间里，一切都是真的。好的。这就是为什么允许一个矛盾是如此可怕。它摧毁了整个数学系统。好的。哥德尔不完全性定理是基于

关注这样一个事实，即每一个数学系统要么是矛盾的，要么是不一致的，你不能证明每一个真理。每个人都立即接受它一定意味着你不能证明每一个真理，因为那个不会破坏数学系统。它通常被认为是不幸的，这实际上是不幸的，因为它被认为是不幸的，但无论如何，它通常被认为是不幸的。

但是每个人都明白，一旦你说我允许一个矛盾，砰，整个数学系统就毫无意义了，对吧？不幸的是，量子物理学也是如此。如果所有物理学都建立在量子物理学之上，并且它允许非显式，

解释性的，它对其中的某些现象没有解释，那么绝对任何东西都可以放在那里，因为原理相同，对吧？这是说，既然我没有解释，我可以插入任何我想要的解释，对吧？在这一点上，它们都同样好。无论如何，这可能是未来播客的一个预览，当我谈论这个的时候。

这也是多世界解释实际上对理解量子物理学非常重要的原因之一。对。因为它实际上解释了所有这些事情，并且它基本上消除了神秘主义，对吧？它说，不，这是解释。而且它完全，并不是那么难理解。你不能理解量子力学的想法是不正确的。它并不难理解。只是……

它存在多个世界，这就是正在发生的事情……无论如何，我认为始终将所有事情都与真正优秀的科幻小说联系起来非常重要……所以……在……维纳·文奇，我认为你知道他是我的最喜欢的科幻小说作家之一，而且非常……

他处理这些限制的方式是在他，至少在他创造的一个宇宙中，创造了他所谓的思想区域的概念，其中

不同的东西，物理定律不同，我们生活在其中的慢速区域，生物智能是可能的，但人工智能、超光速旅行是不可能的，超光速通信是不可能的，直到你到达下一个

宇宙中的实际物理空间，在那里像人工智能，真正的人工智能是可能的。然后，当你继续进入宇宙的其他区域时，你会到达他称之为超越的高级区域，在那里生活着超智能生物，远远超出了我们甚至能够理解的概念。是的。有趣。

这就是他如何绕过这个限制，因为他完全承认这一点，并说这是他唯一能想到的克服物理限制的方法，只是创造那些定律不同的场所。

有趣。而且你知道吗？这并非完全没有道理。如果物理定律不同，我们可以建造不同类型的计算机来计算不同的东西。那是……我顺便提到了这一点，我们可以设想计算机，但我们只是……

是非图灵机的，但它们违反了物理定律。这实际上意味着，如果你有一套不同的物理学，你可以建造不同的计算机，它们具有不同的算法库。对。所以《深海》是特别的小说，他深入探讨了这个问题。推荐一下。《深海》。好的。我必须把它添加到我的收听列表中。好的。

好的，那么让我们今天就到这里吧。好的。感谢大家收听我们的节目。