第一章 程序设计语言？和可计算函数 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.6Ackermann函数 28
2.7字函数的可计算性 33
习题 36
第三章 通用程序 39
3.1程序的代码 39
3.2停机问题 41
3.3通用程序 42
3.4递归可枚举集 45
习题 48
4.1 Turing机的基本模型 50
第四章 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
7.1 Chomsky谱系 90
第七章 正则语言 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.1Turing机的运行时间和工作空间 138
9.2计算复杂性类 141
9.3复杂性类的真包含关系 144
习题 146
第十章 NP完全性 147
10.1 P与NP 147
10.2多项式时间变换和NP完全性 151
10.3 Cook定理 153
10.4若干NP完全问题 157
10.5 coNP 168
习题 170
第十一章 NP类的外面 171
11.1 PSPACE完全问题 171
11.2一个难解问题 176
习题 179
第十二章 P类的里面 180
12.1若干例子 180
12.2对数空间变换 183
12.3 NL类 185
12.4 P完全问题 189
习题 192
第十三章 随机算法与随机复杂性类 193
13.1随机算法 193
13.2随机复杂性类 200
习题 207
附录 208
附录A 记号 208
附录B 中英文名词索引 213
参考文献 221