第一部分
基本复杂性类
第1章
计算模型——为什么模型选择无关紧要
初看起来，为计算建立数学模型可谓难上加难。这是由于，历史上人类在解决各种计算任务的过程中用尽了各种各样的方法——从直觉和灵感到算盘或计算尺，再到现代的计算机。此外，自然界中其他生物或系统也时刻需要处理各种计算任务，而它们的解决之道也是纷乱繁杂。怎样才能找出一个能抓住这些计算方法共性的简洁的数学模型呢？如果再考虑到本书要关注的计算效率问题，则建模问题就更加无从下手了。考虑计算效率问题似乎必须小心地选择计算模型，因为即便是孩童也知道一款新的视频游戏是否能“高效运行”将依赖于他的计算机硬件。
令人惊讶的是，一个简洁的计算模型——图灵机足以研究关于计算及其效率的所有问题。将讨论范围仅限于这种计算模型的理由是充分的，因为它能够模拟所有能被物理实现的计算方法而仅在计算效率上略有损失。因此，图灵机“能高效解决”的计算任务至少与其他计算方法能高效解决的计算任务一样多（一个可能的例外是第10章讨论的量子计算机模型，但目前还不清楚它能否被物理实现）。
本章将给出图灵机的形式定义，并研究它的一些基本性质。1.1节概述了图灵机模型及其基本性质。该小节还为普通读者概述了1.2节至1.5节的结论，以帮助这些读者跳过图灵机模型杂乱的细节而直接从1.6节开始进入复杂性理论。
由于复杂性理论 “complexity”一词译做“复杂性”或“复杂度”。当比较抽象地论及“complexity”时译作“复杂性”，当用具体函数论及“complexity”的高低时，译作“复杂度”。关注的是计算效率，因此1.6节给出了本书最重要的几个定义之一，亦即复杂性类P的定义，它从数学上刻画了由所有能被高效求解的判定问题构成的集合。1.6节还就下面的问题展开了一些讨论：类P是否真的刻画了“高效计算”这一非正式概念的本质。该小节还表明了图灵机的定义是如何贯穿全书的；同时还指出，类P是定义很多其他模型的出发点，这些模型包括非确定型图灵机、概率型图灵机、量子图灵机、布尔线路、并行计算机、判定树和通信游戏，其中有些模型用于研究物理计算的有争议的实现模式，而另一些则主要用于深入理解图灵机计算的本质。
1.1 计算的建模：你真正需要了解的内容
形式地讨论图灵机将不可避免地遇到一些单调乏味的概念。我们先概述这些直觉概念，以便普通读者可以跳过正式的讨论而直接进入从1.6节开始的复杂性理论。当他们在阅读后续章节的过程中偶尔遇到确实需要图灵机模型的细节时，可以随时回头阅读跳过的小节。
千百年来，“计算”这个词曾一直被理解为将机械的规则作用于操作数上，其中完成操作的人或机器允许使用演草纸来记录中间结果。图灵机是这种直觉概念的具体实现。1.2.1节表明，图灵机等价于任何一种现代程序设计语言——除了对内存大小没有限制之外。
下面，我们按照本章开头所引用的图灵的话非正式地描述图灵机模型。令f是一个以位串（即{0,1}中的成员）为输入而以0或1为输出的函数。计算f的一个算法是一组机械的规则，根据这组规则我们可以为任意输入x∈{0,1}计算函数值f(x)。所采用的计算规则是固定不变的（即同一组规则必须适用于所有输入），尽管其中每条规则被使用的次数是任意的。每条规则将用到如下定义的一个或多个“基本”操作：
1.从输入中读取一个位；
2.从算法使用的演草纸或工作空间中读取一个位（也可能是某个更大的字母表中的一个符号，例如集合{0,…,9}中的一个十进制位）。
根据读取的值，
1.在草稿纸上写出一个位或符号；
2.要么停机并输出0或1，要么重新选择下一步要执行的计算规则。
最后，图灵机的运行时间指的是上述基本操作被执行的次数。我们采用渐进术语描述运行时间。因此，如果图灵机在长度为n的输入上至多执行T(n)个基本操作，则称该图灵机的运行时间为T(n)。
下面列举图灵机模型的一些简单事实。
4.简单地利用前面两个事实可以证明，存在不能被任何图灵机计算的函数，见1.5节。不可计算性与著名的哥德尔不完全定理关系密切，见1.5.2节。