Introduction to the theory of computation导论

断断续续接触了自动机，automata, DFA, NFA, Context-free grammars，于是读了读<<Introduction to the Theory of Computation>>。以下是自己对前言的翻译，增强理解。
后续写写学习后的实践心得。
有一些翻译拿不准：
capacities, 容量？能力？
practical concerns 实践考量？
本文括号带英文的某些词。

一些名词对照

computation， 计算

theory of computation，计算理论

computer，计算机

下面翻译开始，

我们从本书呈现的计算理论的概览(overview)出发。跟随着这，你将会有机会学习并且/或者回顾一些你将会用到的数学概念。

Automata, Computability, and Complexity

本书专注于计算理论的三个传统核心方面：automata（自动机）， computability(可计算能力），complexity(复杂度）。它们因下面的问题关联在一起——

计算机最基本的容量(capacities)和限制(limitations)是什么?

这个问题可以追溯回1930年代，那时的数学逻辑学家首先探索计算的意义。从那时起，技术的发展极大地提高了我们计算的能力，并且把这个问题从理论的领域带到了关于实践考量(practical concern)的世界。

在每个方面——automata, computability, complexity——对这个问题的解释不一样，而答案也因解释不一样而变化。接着这个导论，我们在不同的章节探索每一个方面。在这里，我们以倒序的方式介绍它们， 因为从结尾开始，你可以更好地从开始就理解其中的理由。

Complexity Theory (复杂度理论）

计算机问题是不同的：有的容易，有的困难。比如，排序问题是简单的。假设你要对一列数进行升序排列。即使一个很小的计算机也可以快速地将一百万数据排列好。将排序与调度（scheduling)问题做比较。假设你要给整个大学的课程按照一定的约束条件进行布置（schedule)，如在同一个时刻不能有两个课程在同一个教室。调度问题看上去比排序问题困难得多。如果你有一千堂课，那么寻找最好的布置，可能要花几个世纪，即使是用一个超级电脑。

是什么导致了一些问题容易，而另外一些困难？

这是复杂度理论的核心问题。值得注意的是，尽管这个问题被有意思地研究了40多年，我们仍不知道这个问题的答案。后面，我们将讨论这个美妙的问题和它的后果。

目前为止，复杂度理论的研究成果之一是，研究者发现了一个漂亮的方法将问题根据它们的复杂度进行分类。这类似于使用周期表将元素根据它们的化学性质进行分类。使用这个方法，我们可以说明（demonstrate)一个证明某些问题计算起来很困难的论述，即使我们无法证明它们的确如此。

当你面对一个显得计算困难的问题，你有几个选择。第一，明白哪一个方面是问题困难的的根本，所以你可能可以改变它，问题也因此也变得更容易。第二，你可以得到一个不那么完美的解决方案。第三，有些问题只有在最坏情况情况下困难，但是大多数时候都简单。取决于应用场景，你可能可以接受一个偶尔很慢，但是通常跑得很快的办法。最后，你可能可以考虑另外一种计算类型，比如随机化，可以加速某些任务。

某一个被应用复杂度理论直接影响的领域是有年代的密码学。在大多数领域，相对于困难的问题，简单的计算问题更受喜欢，因为它容易解决。密码学是不寻常的，因为它特别需要困难的计算问题。如果没有密码，秘密必须很难被破解。复杂度理论已经向密码学家指明了计算复杂的问题——他们据此设计了革命性的新密码。

Computability Theory （计算能力理论）

在二十世纪上半叶，数学家，如 Kurt Go ̈ del, Alan Turing, and Alonzo Church 发现某些基本的问题不能被计算机解决。这个现象的一个例子是确定一个数学断言是真的还是假的。这个任务是数学的水和空气（英文是bread and butter)。它看起来是一个自然的计算机解决方案（ a natural for solution by computer ），因为它严格地属于数学领地。但是没有一个计算机算法可以解决它。

这个深远影响的结果之一是关于计算机的理论模型的发展——因此，最终引出了真正的计算机的构造。

计算能力和复杂度是紧密联系的。复杂度理论的目标，是将问题分类为简单和困难的；而在计算能力理论里，问题的分类是根据可以解决和不可以解决(solvable)。计算能力理论引入一些在复杂度理论使用的概念。

Automata Theory （自动机理论）

自动机理论处理的是计算的数学模型定义和性质。这些模型在几个应用计算机科学里面起到重要作用。其中一个，叫有限状态机，被用于文本处理，编译器和硬件设计。另外一个模型，叫上下文无关语法，被用于编程语言和人工智能。

自动机理论是开启计算理论学习的绝佳之地。计算能力理论和复杂度理论需要一个“计算机”的准确定义。自动机理论允许实践计算的严谨定义( allows practice with formal definitions of computation)，因为它引入了与其他计算机科学非理论相关领域的概念。

导论翻译结束

本书英文不推荐新手阅读。中文不知道，因为没读过。