还没有笔记
选中页面文字后点击「高亮」按钮添加
我们首先概述计算理论中我们将在此课程中介绍的那些领域。随后，您将有机会学习和/或复习一些您稍后将需要的数学概念。
本书侧重于计算理论中三个传统上处于核心地位的领域：自动机、可计算性和复杂性。它们由以下问题联系在一起：
这个问题可以追溯到1930年代，当时数学逻辑学家首次开始探索计算的含义。自那时以来的技术进步极大地增强了我们的计算能力，并将这个问题从理论领域带入了实际关注的世界。
在这三个领域——自动机、可计算性和复杂性——中，这个问题有不同的解释，答案也因解释而异。在本介绍性章节之后，我们将逐一探讨每个领域，在
本书的一个独立部分中。在这里，我们以倒序介绍这些部分，因为从结尾开始，您可以更好地理解开头的原因。
计算机问题有多种多样；有些容易，有些困难。例如，排序问题是一个简单的问题。假设您需要将一列数字按升序排列。即使是一台小型计算机也能相当快地对一百万个数字进行排序。将其与调度问题进行比较。假设您必须为整个大学找到一份课程表，以满足一些合理的约束条件，例如没有两门课程在同一时间在同一房间进行。调度问题似乎比排序问题要困难得多。如果您只有一千门课程，即使使用超级计算机，找到最佳时间表也可能需要几个世纪。
这是复杂性理论的核心问题。值得注意的是，我们不知道答案，尽管它已被深入研究了40多年。稍后，我们将探讨这个引人入胜的问题及其一些影响。
迄今为止，复杂性理论的一项重要成就，是研究人员发现了一种优雅的方案，用于根据计算难度对问题进行分类。它类似于元素周期表，用于根据化学性质对元素进行分类。利用这种方案，我们可以展示一种方法，为某些问题在计算上是困难的提供证据，即使我们无法证明它们是。
当您遇到一个似乎在计算上很困难的问题时，有几种选择。首先，通过了解问题的哪个方面是困难的根源，您可以对其进行修改，使问题更容易解决。其次，您可以接受一个不完美的解决方案。在某些情况下，找到只近似于完美解决方案的方法相对容易。第三，有些问题只在最坏情况下困难，但大多数时候都容易。根据应用，您可能对偶尔慢但通常运行快速的程序感到满意。最后，您可以考虑替代的计算类型，例如随机化计算，它可以加速某些任务。
复杂性理论直接影响的一个应用领域是古老的密码学。在大多数领域，一个容易的计算问题比困难的问题更受欢迎，因为容易解决的问题成本更低。密码学是不同寻常的，因为它专门需要计算上困难而非容易的问题。秘密代码应该在没有密钥或密码的情况下难以破解。复杂性理论为密码学家指明了计算上困难问题的方向，他们围绕这些问题设计了革命性的新代码。
在二十世纪上半叶，库尔特·哥德尔（Kurt Gödel）、艾伦·图灵（Alan Turing）和阿隆佐·丘奇（Alonzo Church）等数学家发现，某些基本问题无法通过计算机解决。这种现象的一个例子是确定一个数学陈述是真还是假的问题。这项任务是数学家的主要工作。它似乎很适合通过计算机解决，因为它严格属于数学领域。但没有任何计算机算法可以执行这项任务。
这项深刻结果的后果之一是发展了关于计算机理论模型的思想，这些思想最终有助于实际计算机的构建。
可计算性理论和复杂性理论密切相关。在复杂性理论中，目标是将问题分类为容易的和困难的；而在可计算性理论中，问题的分类是根据那些可解决的和那些不可解决的。可计算性理论引入了复杂性理论中使用的几个概念。
自动机理论处理计算数学模型的定义和性质。这些模型在计算机科学的几个应用领域中发挥作用。其中一个模型，称为有限自动机，用于文本处理、编译器和硬件设计。另一个模型，称为上下文无关文法，用于编程语言和人工智能。
自动机理论是开始学习计算理论的绝佳起点。可计算性理论和复杂性理论都需要对计算机进行精确定义。自动机理论通过引入与其他非理论计算机科学领域相关的概念，允许练习形式化计算定义。