第一章 程序设计语言？和可计算函数 1
1.1 预备知识 1
1.2 Church-Turing论题 2
1.3 程序设计语言？ 3
1.4 可计算函数 9
1.5 宏指令 10
习题 12
第二章 原始递归函数 13
2.1 原始递归函数 13
2.2 原始递归谓词 17
2.3 迭代运算、有界量词和极小化 18
2.4 配对函数和G？del数 22
2.5 原始递归运算 24
2.6 Ackermann函数 28
2.7 字函数的可计算性 33
习题 36
第三章 通用程序 39
3.1 程序的代码 39
3.2 停机问题 41
3.3 通用程序 42
3.4 递归可枚举集 45
习题 48
第四章 Turing机 50
4.1 Turing机的基本模型 50
4.2 Turing机的各种形式 55
4.3 Turing机与可计算性 60
4.4 Turing机接受的语言 63
4.5 非确定型Turing机 65
习题 67
第五章 过程与文法 69
5.1 半Thue过程 69
5.2 用半Thue过程模拟Turing机 70
5.3 文法 72
5.4 再论递归可枚举集 75
5.5 部分递归函数 77
5.6 再论Church-Turing论题 78
习题 79
第六章 不可判定的问题 80
6.1 判定问题 80
6.2 Turing机的停机问题 81
6.3 字问题和Post对应问题 83
6.4 有关文法的不可判定问题 86
6.5 一阶逻辑中的判定问题 86
习题 89
第七章 正则语言 90
7.1 Chomsky谱系 90
7.2 有穷自动机 93
7.3 有穷自动机与正则文法的等价性 101
7.4 正则表达式 103
7.5 非正则语言 109
习题 110
第八章 上下文无关语言 112
8.1 上下文无关文法 112
8.2 Chomsky范式 115
8.3 Bar-Hillel泵引理 119
8.4 下推自动机 121
8.5 上下文无关文法与下推自动机的等价性 126
8.6 确定型下推自动机 129
8.7 上下文有关文法 134
习题 136
第九章 时间复杂性与空间复杂性 138
9.1 Turing机的运行时间和工作空间 138
9.2 计算复杂性类 141
9.3 复杂性类的真包含关系 144
习题 147
第十章 NP完全性 148
10.1 P与NP 148
10.2 多项式时间变换和NP完全性 152
10.3 Cook定理 154
10.4 若干NP完全问题 158
10.5 coNP 169
习题 171
第十一章 NP类的外面 172
11.1 PSPACE完全问题 172
11.2 一个难解问题 177
习题 180
第十二章 P类的里面 181
12.1 若干例子 181
12.2 对数空间变换 184
12.3 NL类 185
12.4 P完全问题 189
习题 193
第十三章 随机算法与随机复杂性类 194
13.1 随机算法 194
13.2 随机复杂性类 201
习题 208
习题解答 209
附录 243
附录A 记号 243
附录B 中英文名词索引 248
参考文献 256