Computer Science · An Overview · Chapter 12
计算理论
THEORY OF COMPUTATION
计算理论研究计算机能做什么、不能做什么——它为计算机科学奠定了真正的科学地位。有些问题注定无解，有些问题难解到近乎无解，而"难"本身也能成为守护秘密的基石。
计算理论研究计算机能做什么、不能做什么——它为计算机科学奠定了真正的科学地位。有些问题注定无解，有些问题难解到近乎无解，而"难"本身也能成为守护秘密的基石。
本章讨论计算机能做什么、不能做什么——即研究计算机的能力。一切从"函数"开始：我们解决问题的手段，就是计算函数。
函数 function：一组可能输入值与一组可能输出值之间的对应关系，它使每个可能的输入被赋予单个输出。函数的计算 computation：对于一个给定的输入，确定其具体输出值的过程。
对函数进行计算的能力非常重要：我们能解决问题的手段就是计算函数。因此计算机科学的一个基本任务，就是找出要解决的问题背后的函数。例：排序问题背后就是"乱序表 → 有序表"这个函数。
把函数的输入和输出预先记录在一个表中，需要输出时只需按输入查表。这种系统很方便，但功能有限——许多函数（如 f(x)=x+1，输入有无穷多个）无法完全表示成表格。
遵循代数式提供的方向，把输入/输出组合现场计算出来，如 f(x)=2x²+3x+1。这种方法更有效，但有些函数的输入/输出关系太过复杂，根本不能用代数运算来描述。
可计算函数 computable function：可以依据输入值通过算法来确定其输出值的函数。机器只能执行由算法描述的任务，所以对可计算函数的研究即是对机器能力的研究。
不管函数的复杂性如何，我们是否总能找到一个系统来计算它们？答案是否定的。不可计算函数：计算超出了任何算法系统的能力范围而无法计算的函数。
图灵机由艾伦·图灵于 1936 年提出——比第一台电子计算机还早，是先有理论、后有机器。它是被用作研究算法能力的一种工具。
图灵机 Turing machine：由一个控制单元组成，它能够通过一个读/写磁头对磁带上的符号进行读和写。磁带两端可以无限延伸，并分成一个个单元，每个单元可以包含符号的任意一个有限集合，这个集合称为机器的字母表 alphabet。
每一步都：① 观察当前磁带单元的符号；② 将符号写进这个单元；③ 可能将读/写磁头左移或右移一个单元；④ 改变状态。要执行的确切操作由程序决定——程序通过"机器的状态 + 磁带当前单元的内容"告诉控制单元做什么。
计算开始于一个特定的状态，称为初始状态 initial state；停止于另一个特定状态，称为停止状态 halt state。磁带上的符号串是输入，停机时磁带上的内容就是输出。
图灵可计算函数：以图灵机的方式计算的函数。图灵机的计算能力囊括了任何算法系统的能力：可计算函数等同于图灵可计算函数。图灵机被确立为标准——能计算所有图灵可计算函数的系统，就和任何计算系统一样强大。
通用程序设计语言（universal programming language）：指用来表达计算所有图灵可计算函数的指令性程序设计语言。它包含在高级语言之中，是高级语言的基础和内核。
Bare Bones 语言是从通用程序设计语言中分离出来的需求的最小集合——它是通用程序设计语言的核心，已经不能再"分割"下去了。用它写实用程序并不合适，但它确实能写出任何可计算的程序。
每种高级语言实质上都包含 Bare Bones 语言的特性并将其作为核心——正是这个核心保证了每种语言的通用性，其余特性都是为了方便使用才引入的。
学习 Bare Bones 的目的，是加深对高级程序设计语言的理解——知道它们能够解决计算问题的基本原理：剥掉语法糖，剩下的内核不过如此。
Bare Bones 没有 copy 指令，但可以用两个 while 循环加一个辅助变量实现等效效果——于是教材把 copy name1 to name2 当作速写记号。这正是高级语言"个性"由内核搭出来的缩影。
一个函数，不是图灵可计算的；根据丘奇—图灵论题，它在一般意义上也不可计算——这个函数的计算超出了计算机的计算能力。
停机问题 halting problem：要提前预测到当一个程序在某个条件下开始后，是否能够终止（或者说停止）的问题。停机问题只是不可计算函数的一个实例——背后的"停机函数"：输入是程序的编码，自终止的程序输出 1，否则输出 0。
关键技巧：让程序以"自己的编码"作为输入运行。能停 = 自终止（self-terminating）；不停 = 非自终止。对某个具体程序，我们常能单独判断——但停机问题要的是一个对所有程序都管用的通用算法。
SECTION 12.5
同一台图灵机既能几秒算出结果、也能算到天荒地老——差别在于问题本身的“难度”。这一节用时间复杂性给问题分级：P（多项式时间可解）、NP（非确定性多项式）、NP 完全（NP 中最难），并引出计算机科学最著名的悬案——P 是否等于 NP。
中：解决一个问题所需执行的指令条数（随输入规模增长的趋势）。与之并列的还有空间复杂性 space complexity（所需存储空间），它永远不会比时间增长得更快。
例：顺序搜索 n 个名字约需 n 次比较 → Θ(n)；二分搜索只需 Θ(log₂ n)。
中：若从某项起 f(n) 始终不超过 g(n) 的常数倍，就说 f(n) 以 g(n) 为界，记 f(n) ∈ Θ(g(n))。它忽略常数与低阶项，只抓“增长级别”。
例：3n²+5n 与 100n² 同属 Θ(n²)；归并排序 ∈ Θ(n·log₂ n)。
中：用该问题最优（最简单）解法的复杂性来定义问题本身的复杂性——笨算法慢不代表问题难。
例：在已排序名单中查找，复杂性是 Θ(log₂ n)（二分），而不是顺序搜索的 Θ(n)。
中：其解的复杂性以多项式为界的问题，称为多项式问题，全体记作 P。多项式时间被视为“合理时间 reasonable time”，P 问题被认为是易解的 tractable。
例：排序 Θ(n·log₂ n)、查找 Θ(log₂ n)、两点间最短路——都属于 P。
中：不在 P 中的问题——最优解也需要指数级（如 2ⁿ）甚至更多时间，实际中无法求解大规模实例。
例：从 n 人中列出所有可能的小组有 2ⁿ−1 个，n=50 时穷举需上万年；“x+y=z 吗”若 x,y 是任意实数也永不可答。
中：含有非确定性指令的算法：同一输入在不同执行中可采取不同动作（仿佛能“幸运地猜对”）。它不是日常程序，而是分析问题难度的理论工具。
例：“猜一个满足条件的小组，再验证”——验证是多项式的，猜对靠运气。
中：由非确定性算法在多项式时间内可解的问题构成 NP。显然 P ⊆ NP（确定性算法只是不“猜”的特例），但是否 P = NP 无人知晓。
例：旅行商问题——猜一条路线并验证它是否足够短，验证只要多项式时间。
中：求一条访问每座城市恰好一次、且总长度不超过给定上界的巡回路线。它属于 NP，且已被证明是 NP 完全的。
例：快递配送、电路板钻孔路径规划，都是它的化身。
中：NP 中“最难”的一批问题：只要其中任何一个存在多项式时间的确定性解，所有 NP 问题都有，即 P = NP。
例：旅行商问题、图着色、背包问题——几十年来无人找到多项式解，也无人能证明不存在。
中：“容易验证答案的问题，是否也容易求解？”——这是计算机科学最著名的未解难题（悬赏百万美元的千禧年难题之一）。主流猜测是 P ≠ NP。
例：若 P = NP，则 RSA 等基于“难分解”的密码体系将瞬间崩塌。
中：面对难解问题，人们转而寻找足够好的近似解，而非精确解——这是人工智能与工程实践中的常用策略。
例：自然语言理解的句法识别、网络路由选择、下棋程序的走子决策都用启发式。
中：所有问题 → 可解 / 不可解（停机问题）；可解问题 → 易解（P）/ 难解；NP 介于其间，NP 完全问题是 NP 难度的顶峰。
例：排序 ∈ P ⊂ NP ⊂ 可解问题；停机问题在“可解”之外。
SECTION *12.6
本章是选学内容，却是计算理论最漂亮的应用：利用“正向容易、逆向极难”的计算不对称性，让加密密钥可以公开而解密仍然安全——这就是 RSA 公钥密码体制，也是今天网上银行、HTTPS 的数学基石。
中：最著名的公钥加密体制（以三位发明者姓氏命名），1977 年提出，至今仍广泛用于安全通信。
例：浏览器地址栏的小锁（HTTPS）、数字签名背后常有 RSA 或其近亲算法。
中：公钥密码体制中，加密密钥（公钥，记 (e, n)）可以广泛分发，解密密钥（私钥，记 (d, n)）必须保密。知道公钥并不能推出私钥。
例：你把公钥挂在主页上，任何人都能给你发加密邮件，但只有你能读。
中：① 选两个不同的大素数 p、q；② 令 n = p×q；③ 选取 e、d，使 e×d = k(p−1)(q−1) + 1（k 为某整数）。公钥 = (e, n)，私钥 = (d, n)。
记号：x % m 表示 x 除以 m 的余数（取模）。
中：把消息编码为数值 m，加密得密文 c = mᵉ % n；解密算 cᵈ % n = mᵉˣᵈ % n = m。数学依据是 1 = mk(p−1)(q−1) % pq（欧拉定理的推论）。
例：e×d = k(p−1)(q−1)+1，故 mᵉˣᵈ % n = m¹ = m，原文完璧归赵。
中：攻击者只知 (e, n)，要推出 d 必须先把 n 分解回 p、q。当 n 有数百位二进制位时，大数分解即使用超级计算机也要数年——这就是 12.5 节“难解问题”的实战价值。
例：至今没有人找到不掌握密钥却能有效解密 RSA 的方法。
中：难解问题并非总是坏事——密码学正是利用“正向计算易、逆向求解难”的不对称性构筑安全。若有一天 P = NP 且分解变容易，整个体系就需重建。
例：量子计算的 Shor 算法能高效分解大数，因此“后量子密码”已成为研究热点。
ANSWER KEY
12 道课堂练习题的参考答案速查。建议先独立完成，再对照解析查漏补缺。
GLOSSARY