目录 1
第一章 预备知识 1
1．集合与n元组 1
2．函数 2
3．字母表和字符串 2
4．谓词 3
5．量词 4
6．反证法 5
7．数学归纳法 6
第一部分 可计算性 11
第二章 程序和可计算函数 11
1．一种程序设计语言 11
2．几个程序例子 12
3．句法 17
4．可计算函数 19
5．再论宏指令 21
第三章 原始递归函数 24
1．合成 24
2．递归 24
3．PRC类 25
4．若干原始递归函数 26
5．原始递归谓词 29
6．迭代运算和有界量词 30
7．极小化 32
8．配对函数和哥德尔数 35
第四章 通用程序 38
1．用数作为程序的编码 38
2．停机问题 40
3．通用性 41
4．递归可枚举集 44
＊5．参数定理 47
＊6．递归定理 49
＊7．Rice定理 50
第五章 字符串的计算 52
1．字符串的数字表示 52
2．一种用于字符串计算的程序设计语言 57
3．语言？和？ 60
4．波斯特-图灵程序 61
5．用？模拟？ 65
6．用？模拟？ 69
第六章 图灵机 72
1．内部状态 72
2．通用图灵机 76
3．图灵机接受时语言 76
4．图灵机的停机问题 78
5．非确定型图灵机 79
6．图灵机的变种 81
第七章 过程和文法 87
1．半图厄过程 87
2．用半图厄过程模拟非确定型图灵机 88
3．不可解的字问题 91
4．波斯特的对应问题 94
5．文法 98
6．一些和文法有关的不可解问题 102
7．递归和极小化 103
＊8．正规过程 106
＊9．非递归可枚举集 108
第二部分 文法与自动机 111
第八章 正则语言 111
1．有穷自动机 111
2．非确定型有穷自动机 113
3．附加数例 116
4．封闭性 118
5．Kleene定理 119
6．泵引理及其应用 123
7．Myhill-Nerode定理 124
1．上下文无关文法及其推导树 127
第九章 上下文无关语言 127
2．正则文法 134
3．乔姆斯基规范形式 137
4．Bar-Hillel泵引理 139
5．封闭性 141
＊6．可解和不可解问题 144
7．括号语言 147
8．下推自动机 152
9．编译程序和形式语言 159
第十章 上下文有关语言 162
1．乔姆斯基层次 162
2．线性有界自动机 163
3．封闭性 167
第十一章 命题演算 171
1．公式和赋值 171
第三部分 逻辑 171
2．重言推理 174
3．范式 175
4．Davis-Putnam规则 179
5．极小不可满足性和归类 183
6．消解法 183
7．紧致性定理 185
1．谓词逻辑语言 187
第十二章 量词理论 187
2．语义学 188
3．逻辑结论 191
4．Herbrand定理 194
5．合一 202
6．紧致性与可数性 205
＊7．哥德尔不完全性定理 206
＊8．谓词逻辑？可满足性问题的不可解性 208
第十三章 循环程序 213
1．语言L和原始递归函数 213
第四部分 复杂性 213
2．运行时间 217
3．把？作为层次 221
4．定界定理的逆 225
＊5．不带转移指令进行工作 228
第十四章 抽象复杂性 230
1．Blum公理 230
2．间隙定理 232
3．加速定理的初级形式 234
4．最终形式的加速定理 239
第十五章 多项式时间可计算性 242
1．增长率 242
2．P与NP 245
3．Cook定理 248
4．其它NP完全问题 252
第十六章 不可解问题的分类 255
1．使用外部信息源 255
第五部分 不可解性 255
2．通用性的相对化 257
3．可归约性 261
4．相对于外部信息源的r？e？集 264
5．算术层次 267
6．波斯特定理 268
7．某些不可解问题的分类 273
8．再论Rice定理 277
9．递归排列 278
第十七章 不可解级和波斯特问题 281
1．图灵级 281
2．克林-波斯特定理 283
3．创造集和Myhill定理 285
4．单纯集和Dekker定理 291
5．Sacks裂解定理 294
6．优先法 296
对进一步阅读的建议 301
英中名词对照表 303