计算理论导论

引用

Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.

章节概要

全书分为三个部分，依照这门学科的传统顺序展开：自动机与语言、可计算性理论、复杂性理论。最前面是一个预备性的第0章，每章末尾都有习题、问题与解答。作者把本书描述为面向高年级本科生或研究生入门课程的教材，涵盖自动机理论、可计算性理论和复杂性理论。

第0章：引言

开篇一章汇集全书用到的数学背景，包括集合和图，并配有编号的例子和问题。书中先给出定义和定理的形式化陈述并加以证明的做法，从这里开始确立。

第一部分，第1–2章：自动机与语言

第1章“正则语言”引入最简单的计算模型及其所识别的语言。第2章“上下文无关语言”进入表达能力更强的下一个层次。第三版在这里新增一节，讨论确定性上下文无关文法；出版社称之为首创的理论处理，与语法分析和LR(k)文法相联系。

第二部分，第3–6章：可计算性理论

第3章“丘奇–图灵论题”引入图灵机，作为算法能做什么的标准模型。第4章“可判定性”追问哪些问题根本上能被这类机器解决。第5章“可归约性”把归约发展为证明更多问题不可判定的主要工具。第6章“可计算性理论的高级专题”在核心序列之外扩展了更多结果。

第三部分，第7–10章：复杂性理论

第7章“时间复杂性”从“什么可以计算”转向“在资源限制内可以计算什么”。第8章“空间复杂性”对存储做同样的讨论。第9章“难解性”考察可证明困难的问题，第10章“复杂性理论的高级专题”以更多专题收尾。

核心概念

第一部分：自动机与语言

• 正则语言：由最简单的计算模型识别的语言，是第1章的主题。
• 上下文无关语言：下一个语言类，是第2章的主题；第三版增加了确定性上下文无关文法。

第二部分：可计算性

• 图灵机与丘奇–图灵论题：代表直观算法概念的形式模型。
• 可判定性：一个问题能否被算法解决。
• 可归约性：通过归约把不可判定性从一个问题传递到另一个问题。

第三部分：复杂性

• 时间与空间复杂性：度量计算所需的资源，是第7、8章的主题。
• 难解性：可证明困难的问题，是第9章的主题。

评析

优点

• 以清晰为主要卖点。 Cengage 称本书保持平易近人的风格，修订及时，增加了习题和更令人印象深刻的例子，同时保持严谨与形式化。
• 用一条路线贯穿三个主题。 各部分遵循大多数课程讲授这些内容的顺序：先自动机，再可计算性，最后复杂性。第3–5章的标题显示，可判定性与可归约性是在图灵机的基础上依次建立的。
• 习题支持。 每章末尾都有习题、问题与解答；第三版增加了新的习题、问题和解答，作者还为该版本维护公开的勘误表。
• 与语法分析的联系。 关于确定性上下文无关文法的新增一节把理论与LR(k)分析联系起来，对在编译原理课上接触过文法的读者很有用。

局限

• 全书以证明为主。 出版社强调其数学处理“包括高深的定理与证明”，因此缺乏证明经验的读者要做好一边学习内容、一边学习写证明的准备。
• 只讲理论。 章节目录中没有基于编程的内容；想通过运行程序来理解可计算性的读者需要另找资料。
• 高级各章有所取舍。 第6章和第10章是若干后续专题的汇集，并不对其中任何一个做完整展开。

在课程中的定位

在本课程书单中，Sipser 是分量适中、以证明为主的核心教材。Peter Linz 与 Susan Rodger 的 An Introduction to Formal Languages and Automata 更为平缓，重解释和例题而轻形式化；John MacCormick 的 What Can Be Computed? 在正式论证之前先用简短的Python程序讲解可计算性与复杂性，适合觉得形式化方法抽象的读者作为第一本书。Dexter Kozen 的 Automata and Computability 以短讲的形式组织，含完整证明和大量分级习题；Hopcroft、Motwani 和 Ullman 的 Introduction to Automata Theory, Languages, and Computation 是范围相近的经典替代品。Arora 与 Barak 的 Computational Complexity 是研究生层次的读物，从第7–10章停下的地方继续。

如何使用本书

本书适合已修过离散数学、能读写证明的高年级本科生和研究生新生。

建议的学习安排：

• 核心： 先读第0章了解记号（熟悉的话可略读），然后依次读第1–5章和第7章。这些构成完整的第一门课：正则语言与上下文无关语言、图灵机、可判定性与归约，以及时间复杂性。
• 接下来： 第8章（空间复杂性）和第9章（难解性）。
• 可选： 若对语法分析感兴趣，可读第2章末尾关于确定性上下文无关文法的部分；时间更长或研究生层次的课程可加入“高级专题”第6章和第10章。
• 练习： 在看解答之前先做每道习题和问题，并用完整的句子写出证明；书中的证明就是范例。请对照作者为你手头版本提供的勘误表。

如果觉得第1–2章太抽象，可以先读一本更平缓或基于程序的书，再回到 Sipser 读第3–5章，那里开始讲可计算性。自学时，可以把第4、5、7章的主要归约和证明套路记在笔记本上；归约和证明套路在各章中反复出现，凭记忆重新推导一遍是检验理解程度的快捷方式。