《可计算性复杂性语言 理论计算机科学基础》求取 ⇩

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

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