What Can Be Computed? A Practical Guide to the Theory of Computation（什么是可计算的：计算理论实用指南）

引用

MacCormick, J. (2018). What Can Be Computed? A Practical Guide to the Theory of Computation. Princeton University Press.

章节概要

全书共十八章：一章导论性概述，讲可计算性理论的第一部分（第2–9章），讲计算复杂性理论的第二部分（第10–14章），讲起源与应用的第三部分（第15–17章），以及一章简短的结语。面向教师的序言讨论了本书适合哪一类理论课程、收录与舍弃了哪些内容，以及可以围绕本书设计哪些课程。出版社称，本书对可计算性和复杂性同等重视，正文使用Python程序（Java版本在网上提供），并以完全严格的方式陈述和证明标准定理；讲义幻灯片和Python程序可在配套网站获取。各章末尾都有习题。

第1章：Introduction: What Can and Cannot Be Computed?（导论：什么能计算，什么不能计算）

把问题分为易解的、难解的和不可计算的三类，更详细地概述全书，并说明先修要求、学习目标以及学习计算理论的理由。

第2章：What is a Computer Program?（什么是计算机程序）

确定第一部分通篇使用的模型："SISO" Python程序，即输入一个字符串、输出一个字符串的程序。本章介绍所需的Python知识、有问题的程序、Python程序的形式定义、判定程序与等价程序，以及现实中的程序与这一模型的关系。

第3章：Some Impossible Python Programs（几个不可能存在的Python程序）

对分析其他程序的程序（yesOnString.py、yesOnSelf.py、notYesOnSelf.py）运用反证法，说明某些程序不可能存在，进而得出结论：完美的查错程序不可能存在，但有用的查错程序仍然可以有。

第4章：What is a Computational Problem?（什么是计算问题）

介绍图、字母表、字符串和语言，定义计算问题及其类别，并给出"求解"问题以及识别和判定语言的形式含义。

第5章：Turing Machines: the Simplest Computers（图灵机：最简单的计算机）

定义图灵机，构造几台非平凡的图灵机，从单带图灵机过渡到多带图灵机，再过渡到Python程序；反过来又用Python模拟图灵机。本章最后指出，经典计算机可以模拟量子计算机，所有已知的计算机都是图灵等价的。

第6章：Universal Computer Programs: Programs That Can Do Anything（通用程序：无所不能的程序）

介绍通用Python程序和通用图灵机、现实世界中的通用计算、修改其他程序的程序，以及不可判定但可识别的问题。

第7章：Reductions: How to Prove a Problem is Hard（归约：如何证明一个问题很难）

介绍用于证明容易性和困难性的归约、图灵归约的形式定义及其性质，并列举一系列不可计算问题，其中包括与程序无关的问题，最后总结证明不可计算性的技巧。

第8章：Nondeterminism: Magic or Reality?（非确定性：魔法还是现实？）

定义非确定型Python程序和计算树，证明非确定性不改变可计算的范围，给出非确定型图灵机的形式定义，并讨论不可识别的问题以及研究非确定性的意义。

第9章：Finite Automata: Computing With Limited Resources（有限自动机：在有限资源下计算）

讨论确定型和非确定型有限自动机及其等价性、正则表达式、非正则语言，以及正则语言的组合。

第10章：Complexity Theory: When Efficiency Does Matter（复杂性理论：当效率真正重要时）

介绍渐近运行时间和大O记号、如何确定程序的运行时间、计算模型对复杂性为何重要，以及复杂性类。

第11章：Poly and Expo: the Two Most Fundamental Complexity Classes（Poly与Expo：两个最基本的复杂性类）

定义Poly类和Expo类，说明它们不依赖于计算模型，给出属于Expo而不属于Poly的问题HALTEX，并讨论不合理的输入编码。

第12章：PolyCheck and NPoly: Hard Problems That Are Easy to Verify（PolyCheck与NPoly：难解却易于验证的问题）

定义多项式时间验证器和PolyCheck类，借助非确定性定义NPoly，证明二者相同，并论证非确定性似乎确实会改变能够高效计算的范围。

第13章：Polynomial-time Mapping Reductions: Proving X is as Easy as Y（多项式时间映射归约：证明X与Y一样容易）

定义多项式时间映射归约，以哈密顿回路问题为例加以说明，并通过归约把CIRCUITSAT、SAT和3-SAT联系起来。

第14章：NP-Completeness: Most Hard Problems Are Equally Hard（NP完全性：大多数难题同样难）

讨论P与NP问题、NP完全性和NP难度、P = NP会带来的后果、作为NP中"最难"问题的CIRCUITSAT（库克–列文定理）、NP完全性的普遍性及其证明技巧。

第15–17章：The Original Turing Machine（最初的图灵机）；You Can't Prove Everything That's True（并非所有真命题都能被证明）；Karp's 21 Problems（卡普的21个问题）

第15章解读图灵1936年对"计算机器"的定义，并讨论丘奇–图灵论题。第16章把不可判定性与机械证明以及哥德尔关于算术不完备性的结果联系起来。第17章逐步梳理卡普关于21个NP完全问题的论文以及这些问题之间的归约。

第18章：Conclusion: What Will Be Computed?（结语：什么将被计算？）

简要回顾关于"什么能被计算"的几个重要思想。

核心概念

第1–4章：程序与问题

• 易解、难解和不可计算的问题：贯穿全书的三种分类。
• SISO Python程序：把一个输入字符串映射为一个输出字符串的程序，是本书的主要计算模型。
• 识别与判定：接受语言中的字符串，与总能停机并给出正确的"是"或"否"之间的区别。

第5–9章：机器、通用性与归约

• 图灵等价：图灵机、Python程序和所有已知计算机能计算的东西相同这一结论。
• 通用程序：能运行作为输入给出的任意其他程序的程序。
• 图灵归约：通过说明解决某问题就能解决一个已知不可计算的问题，来证明该问题不可计算。
• 非确定性：分支成一棵可能性之树的计算；它不扩大可计算的范围。
• 有限自动机与正则表达式：资源有限的计算模型。

第10–14章：复杂性

• Poly与Expo：可在多项式时间和指数时间内求解的问题；这是本书在转向标准的P和NP之前使用的类名。
• 验证器与PolyCheck：能快速检验所给解答的程序，以及具有这种验证器的问题类，后者被证明等于NPoly。
• 多项式时间映射归约：把一个问题高效地转化为另一个问题。
• NP完全性与库克–列文定理：NP中最难的问题，第一个例子是CIRCUITSAT。

第15–18章：起源与应用

• 丘奇–图灵论题：凡是人按规则能计算的，机器也能计算这一主张。
• 不完备性：不可判定性的一个推论，即某些真的算术命题无法被证明。

评析

优点

• 以真实程序为切入点。 出版社的介绍、各章标题以及The Ubyssey上的书评（Angela Tian，2018年8月）都指向同一设计：不可能性、通用性和归约先用读者可以运行的Python程序来论证，然后才给出标准的图灵机表述。
• 内容均衡。 第一部分和第二部分给可计算性和复杂性的篇幅大致相当；复杂性部分从Poly和Expo、验证器和归约一步步铺垫，最后才到NP完全性。
• 超出教学大纲的背景。 第三部分解读图灵的原始论文，把不可判定性与哥德尔不完备定理联系起来，并梳理卡普的21个问题。
• 配套材料。 讲义幻灯片和程序可在配套网站获取；Ubyssey的书评还提到每章末尾的习题，以及对每一文献都有说明的参考书目。

局限

• 形式语言着墨不多。 有限自动机和正则表达式只占一章，上下文无关文法、下推自动机和乔姆斯基层次都不在各章主题之列。涉及这些内容的课程需要另一本教材。
• Python处于前台。 读者需要能熟练阅读Python；Ubyssey的书评也指出，看懂Python示例需要编程经验。
• 非标准的名称。 本书先用自己的Poly、Expo、PolyCheck和NPoly等类展开讨论，再与P和NP联系起来，学生需要把这些名称与其他教材和考试中使用的标准记号对应起来。
• 复杂性止于NP完全性。 从章节标题看，书中没有涉及空间复杂性，也没有涉及随机化或近似等更深入的主题。

在课程中的定位

在计算理论这门课的书单中，本书是最以程序为中心的入门书。另一本入门教材 Linz 与 Rodger 的 An Introduction to Formal Languages and Automata 把大部分篇幅用于自动机、文法和下推自动机，并以语法分析部分收尾；MacCormick 则把这些篇幅用在可计算性和复杂性上。以形式语言为主线的课程，宜以 Linz 与 Rodger 为主教材，用 MacCormick 学习可计算性和NP完全性部分；以"计算机能做什么"为主线的课程，则反过来。

Sipser 的 Introduction to the Theory of Computation、Hopcroft、Motwani 与 Ullman 的 Introduction to Automata Theory, Languages, and Computation 以及 Kozen 的 Automata and Computability 用标准的图灵机记号讲授相同的定理，形式语言理论也更多；在读这些书之前，MacCormick 很适合作为建立直觉的第一遍。Arora 与 Barak 的 Computational Complexity 是研究生教材，对复杂性的讨论远远超出第14章。

如何使用本书

出版社称本书是为初次接触这一学科的本科生编写的，先修要求很少，也适合自学。实际上，学过一门含Python的程序设计入门课，并对反证法有所接触，前几章就会读得很顺。

• 核心： 第1章，然后按顺序读第一部分（第2–8章）和第二部分（第10–14章）。两部分前后衔接，尤其是非确定性（第8章）是NPoly（第12章）的基础。
• 第9章： 如果课程要考查有限自动机，这一章必读；否则可以略读。
• 第三部分： 选读的拓展内容；第16章适合对逻辑和数学感兴趣的学生，第17章适合想多练习NP完全性的学生。

从配套网站下载程序，边读边运行，尤其是第3、6、7章，那里的不可能性论证正是由分析其他程序的程序构建起来的。在读某个程序不可能存在的证明之前，先试着修改一下这个程序。每遇到Poly、Expo、PolyCheck和NPoly，就在旁边写下对应的标准名称，这样转向其他教材时会轻松得多。