序言

“我们不做任何承诺，但我们怀着希望，如往常一样，对无用知识的不懈追求将对未来产生影响。”……“建立使人类后代自由的后代的制度是充分合理的。

这个毕业生或对人类知识做出了有益的贡献。

一首诗，一首交响曲，一幅绘画，一个数学真理，一个新的科学事实，都具有大学，学院和研究所所需要或要求的所有理由”，亚伯拉罕·弗莱克斯纳，《无用知识的实用性》，1939年。

“我建议您选择最困难的课程，因为当您挑战自我时，您会学到最多的知识。CS 121，我发现很难。”，马克·扎克伯格，2005年。

教育目标

这是关于理论计算机科学的本科入门课程的教科书。本书的教育目标是传达以下内容：

  • 这种计算不仅出现在现代的基于硅的计算机中，还出现在各种自然和人为的系统中。

  • 同样，除了成为极其重要的工具之外，计算还可以用作描述自然，物理，数学甚至社会概念的有用镜头。

  • 许多不同计算模型的通用性概念，以及代码和数据之间对偶性的相关概念。

  • 可以精确定义一种数学计算模型，然后用它来证明（或有时仅是推测）下界和不可能结果的想法。

  • 现代理论计算机科学中的一些令人惊讶的结果和发现，包括NP完整性的盛行，交互作用的力量，一方面是随机的力量，另一方面是进行非随机化的可能性，“为了好用硬度”的能力。 ”，以及量子计算的引人入胜的可能性。

我希望通过本课程的学习，使学生能够认识到计算的能力和缺陷，因为它出现在各种环境中，包括看似“静态”的内容或诸如宏和脚本之类的“受限”形式主义。

他们应该能够遵循关于计算的证明逻辑，包括归约化的中心概念，以及理解“自引用”证明（例如，基于对角化的证明，其中涉及以自己的代码作为输入的程序）。

学生应该理解一些问题天生就难以解决，并且在面对新问题时能够认识到潜在的棘手问题。虽然本书仅涉及密码学，但学生应了解如何使用计算硬度进行密码学的基本思想。

但是，这本书比其他任何技能都旨在向学生介绍一种新的计算思维方式，它本身就是一个对象，并说明了这种新思维方式如何带来深远的见解和应用。

我写这篇文章的目的是试图以最简单的方式传达这些概念，并确保形式化的符号和模型有助于阐明而不是使主要思想模糊。

我还尝试利用现代学生对编程的熟悉程度（至少是兴趣！），因此使用（高度简化的）编程语言来描述我们的计算模型。也就是说，本书并不假定您会流利使用任何特定的编程语言，而只是对编程的一般概念有所了解。

我们将使用编程隐喻和惯用语，偶尔提及特定的编程语言，例如Python，C或Lisp，但是即使学生不熟悉这些语言，他们也应该能够遵循这些描述。

本书中的证明，包括通用图灵机的存在，每个有限函数都可以由某个电路，库克-莱文定理和许多其他电路计算的事实，在它们最终涉及到的意义上，通常是构造性和算法性的将一个程序转换为另一个程序。

尽管可以在不看代码的情况下遵循这些证明，但我确实认为，能够访问代码并具有使用它的能力并了解其在各种程序中的作用的能力，可以使这些定理对学生更具体。

为此，一个附带的网站（仍在开发中）允许在我们定义的各种计算模型中执行程序，并查看一些定理的构造证明。

给学生

这本书可能具有挑战性，主要是因为它在计算研究中汇集了各种思想和技术。

无论是遵循对角化论证来证明暂停问题是无法确定的，还是要解决NP完整性降低的组合小工具，分析概率算法，或争论对手来证明密码原语的安全性，都有许多技术障碍需要掌握。

接触该材料的最佳方法是积极阅读这些笔记，因此请确保准备好笔。

阅读时，我建议您停下来思考以下问题：

  • 当我陈述一个定理时，请停下来尝试一下，然后再阅读证明。 即使仅靠自己尝试5分钟，您仍会惊讶于您对证明的理解程度，这会让您感到惊讶。

  • 阅读定义时，请确保您了解该定义的含义，以及满足该定义的对象和不满足该定义的对象的自然示例。 尝试考虑该定义背后的动机，以及是否存在其他自然的方式来形式化同一概念。

  • 积极注意阅读文本时在脑海中出现的问题，以及文本中是否回答了这些问题。

作为一般规则，理解定理比定理更重要，理解定理陈述比证明更重要。

毕竟，在证明一个定理之前，您需要了解它的状态，并且要了解一个定理是关于什么的，您需要了解所涉及对象的定义。只要定理的证明至少有些复杂，我就会提供“证明思想”。可以在初读时随意跳过实际证明，仅关注证明思想。

本书包含一些代码片段，但这绝不是编程文本。您无需知道如何编程即可遵循该材料。我们使用代码的原因是它是描述计算的精确方法。

具体的实现细节对我们而言并不那么重要，因此我们将着重于代码的可读性，但要以诸如错误处理，封装等方面的考虑为代价，这些因素对于现实世界的编程而言极为重要。

付出的努力值得吗？

这不是一本容易的书，您可能会合理地想知道为什么您应该花精力在学习该材料上。

“计算理论”课程的传统理由是，您可能会在以后的职业生涯中遇到这些概念。

也许您会遇到一个难题，并意识到它是NP完整的，或者发现有必要使用从正则表达式中学到的知识。

这可能很正确，但是本书的主要好处不是教给您任何实用的工具或技术，而是给您提供了不同的思维方式：即使在非显而易见的情况下也能够识别计算现象设置，一种对计算任务和问题进行建模并对其进行推理的方法。

无论您有任何用途，您都可以从这本书中获得。

我认为学习此材料很重要，因为它包含了既美观又基础的概念。

能源和物质在20世纪扮演的角色在21世纪通过计算和信息发挥作用，不仅是我们的技术和经济工具，而且是我们用来了解世界的基本构件。这本书将带给您一些背后的理论知识，并希望激发您学习更多的好奇心。

给潜在的教练

我为哈佛课程写了这本书，但我希望其他讲师也会对它有用。

在某种程度上，它的内容类似于“计算理论”或“伟大思想”课程，例如在CMU或MIT教授的课程。

我们的方法与更传统的方法（例如，Hopcroft和Ullman（Hopcroft，Ullman，1969）（Hopcroft，Ullman，1979）和Sipser（Sipser，1997））之间的最大区别是，我们不是从有限自动机开始的初始计算模型。

相反，我们的初始计算模型是布尔电路。

我们认为布尔电路比自动机对计算理论（甚至是实践）更基础。

特别是，布尔电路是人们希望在现代理论计算机科学课程中教授的许多概念的先决条件，包括密码学，量子计算，去随机化，尝试证明 P != NP，等等。

即使在并非严格要求布尔电路的情况下，它们通常也可以提供显着的简化（例如Cook-Levin定理的证明）。

此外，我相信从布尔电路开始而不是有限自动机有很多教学上的原因。

布尔电路是一种更自然的计算模型，它与Silicon中的计算更紧密对应，从而使练习的联系对学生更直接。

有限函数可以说比无限函数更容易掌握，因为我们可以完全写下它们的真值表。每个有限函数可以由布尔电路计算的定理既简单又重要，足以作为本课程的一个很好的起点。此外，在这种情况下，已经可以看到计算理论的许多主要概念点，包括代码和数据之间的对偶性的概念以及通用性的思想。

经过布尔电路后，我们继续使用图灵机，并证明了诸如通用图灵机的存在，停止问题的不可计算性以及莱斯定理等结果。在看到图灵机和不确定性之后，将讨论自动机，作为一个受限计算模型的示例，其中可以有效解决诸如确定暂停的问题。

虽然这不是我们的动机，但我们给出的电路，图灵机和自动机的顺序大致对应于其发现的时间顺序。布尔代数可以追溯到Boole和DeMorgan在1840年代的工作（Boole，1847）（De Morgan，1847）（尽管布尔电路的定义以及与物理计算的联系是90年代后由Shannon（Shannon，1938）给出的）。艾伦·图灵（Alan Turing）在1930年代（图灵，1937年）定义了我们现在所说的“图灵机”，而在1943年McCulloch和Pitts的著作（McCulloch，Pitts，1943年）中引入了有限自动机，但在1959年拉宾和斯科特（Rabin，Scott，1959）。

更重要的是，虽然有限状态机，正则表达式和无上下文语法之类的模型对于实践非常重要，但这些模型的主要应用（无论是用于解析，分析活动性和安全性，甚至是对于软件定义的路由表）至关重要地依赖于以下事实：这些模型易于处理，我们可以有效地回答语义问题。在学生看到了通用计算模型的语义特性的不确定性之后，可以更好地理解这种实践动机。

我们从电路开始的事实使证明Cook-Levin定理变得容易得多。实际上，我们可以使用少数几行Python来证明这一定理。将此证明与标准归约（也用Python实现）相结合，可使学生直观地了解如何将有关计算的问题映射为有关（例如）图中是否存在独立集合的问题。

区别

时间复杂度

为了测量时间复杂度，我们使用算法课程中（隐式）使用的标准RAM机器模型，而不是图灵机。

虽然这两个模型在多项式上当然是等价的，因此对于 P，NP 和 EXP 类的定义没有区别，但我们的选择是区分概念 例如O（n）或 O(n^2)时间更有意义。

这种选择还可以确保这些更细粒度的时间复杂度类别与学生在其算法讲座（或白板编码访谈…）中遇到的线性和二次时间的非正式定义相对应。

减少专用于有限自动机和上下文无关语言的时间，可使教师将更多的时间花在现代计算机理论课程需要涉及的话题上。

其中包括随机性和计算，证明与程序之间的相互作用（包括Gödel的不完全性定理，交互式证明系统，甚至包括\lambdaλ微积分和Curry-Howard对应关系），密码术和量子计算。

功能术语

我们使用功能术语而不是语言。

也就是说，不是说图灵机 M 确定语言 L⊆{0,1}*，我们说它计算函数F：{0,1} *=>{0,1}

“语言”的术语源于乔姆斯基的著作（乔姆斯基，1956年），但通常比阐明更令人困惑。

语言术语也使讨论诸如算法等概念变得麻烦，这些算法可计算具有多于一位输出的函数（包括加，乘等基本任务）。

我们使用函数而不是语言这一事实​​意味着我们必须格外警惕学生区分计算任务的规范（例如，函数）和其实现（例如，程序）。

另一方面，这一点是如此重要，以至于值得反复强调和深入研究学生，无论使用什么符号。

该书确实提到了语言术语，并偶尔提醒它，以使学生更容易查阅外部资源。

本书包含足够的细节，可用于自学。

为此，每一章均以学习目标列表开头，以结尾结尾，并附有“暂停框”，鼓励学生停下来并提出论点，或确保他们理解定义，然后再继续。

第0.5节包含本书的“路线图”，其中包含不同章节的描述以及它们之间的依赖关系结构。

这有助于基于本书计划课程。

致谢

该文本在不断发展，我得到许多人的感谢，对此我深表感谢。

Salil Vadhan与我共同学习了该课程的第一版，并在此过程中为我提供了大量有用的反馈和见解。

Michele Amoretti和Marika Swanberg仔细阅读了本文的几章，并给出了非常有帮助的详细评论。

戴夫·埃文斯（Dave Evans）和理查德·许（Richard Xu）提出了许多请求请求，以修复错误并改善措辞。

感谢Anil Ada，Venkat Guruswami和Ryan O’Donnell在教学CMU 15-251方面的经验提供了有用的提示。

感谢所有向我发送评论，错别字报告，发布问题或在GitHub存储库https://github.com/boazbk/tcs上发出请求的人。

我很高兴在这些注释的制作中使用许多开源软件包。

我特别感谢Donald Knuth和Leslie Lamport的LaTeX，以及John MacFarlane的Pandoc。

David Steurer编写了原始脚本来生成此文本。当前版本使用的是Sergio Correia的长笛。 LaTeX和HTML版本的模板来自Tufte LaTeX，Gitbook和Bookdown。

感谢Amy Hendrickson提供的LaTeX咨询。

Juan Esteller和Gabe Montague最初使用OCaml和Javascript实现了NAND​​ *编程语言。我使用Jupyter项目编写了补充代码段。

最后，我要感谢我的家人：我的妻子拉维特（Ravit）和我的孩子阿尔玛（Alma）和戈伦（Goren）。

编写本书（以及相应的课程）花费了我很多时间，以至于阿尔玛为她的五年级班级写了一篇论文，她说：“大学不应该给教授们过多的工作压力。”恐怕我要做的就是显示600页的超无聊数学文字。

参考资料

preface