《递归论导论》求取 ⇩

第一章 导言和预备知识3

1.1 算法3

1.2 部分函数6

第二章 图灵可计算函数9

2.1 图灵机的基本概念10

2.2 图灵可计算函数15

2.3 正则的图灵机20

2.4 可计算性与函数运算30

习题36

第三章 部分递归函数39

3.1 原始递归函数39

3.2 部分递归函数48

习题51

第四章 通用函数和通用图灵机55

4.1 图灵机的算术化55

4.1.1 图灵机的编号55

4.1.2 瞬时描述的编号58

4.1.3 图灵机的算术化61

4.2 通用函数和通用图灵机63

4.3 对角线方法65

习题68

第五章 s-m-n定理和递归定理69

5.1 丘奇论题69

5.2 s-m-n定理72

5.3 递归定理76

习题77

第六章 哥德尔不完全性定理79

6.1 形式算术79

6.2 PA系统的算术化84

6.3 数字可表示性87

6.4 哥德尔不完全性定理93

第七章 递归可枚举集101

7.1 判定问题101

7.2 递归可枚举集104

习题115

第八章 m-归约和m-度116

8.1 m-归约116

8.2 指标集121

8.3 产生集、创造集和单纯集127

习题133

第九章 图灵度134

9.1 相对可计算性134

9.2 图灵度143

9.3 极限148

习题151

第十章 波斯特问题153

10.1 波斯特问题和单纯集153

10.2 优先方法159

10.3 穆契尼克和弗里德伯格的证明165

习题171

索引173

参考书目178