可计算性复杂性语言 理论计算机科学基础PDF电子书下载

目录 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