可计算函数PDF电子书下载

第一章 可计算函数、可判定集与可数集 1

1.可计算函数 1

2.可判定集 2

3.可数集 4

4.可数集与可判定集 6

5.可数性与可计算性 7

第二章 通用函数与不可判定性 11

1.通用函数 11

2.对角构造 13

3.可数的不可判定集 14

4.可数的不可分集 15

5.单集：Post构造 16

第三章 编号与运算 19

1.Godel通用函数 19

2.可计算函数的可计算序列 22

3.Godel通用集 23

第四章 Godel编号系统的性质 27

1.编号集 27

2.旧函数的新编号 30

3.Godel编号系统的同构 33

4.函数的可数性 35

第五章 不动点定理 39

1.不动点与等价关系 39

2.打印程序文本的程序 41

3.系统的技巧：另一个证明 44

4.几点附注 46

第六章 m-可约性与可数集的性质 51

1.m-可约性 51

2.m-完全集 53

3.m-完全性与有效不可数性 54

4.m-完全集的同构 57

5.产生集 59

6.不可分集的对 62

第七章 Oracle计算 67

1.Oracle机 67

2.相对可计算性：等价描述 69

3.相对化 71

4.0'-计算 74

5.不可比集 77

6.Friedberg-Muchnik定理：构造的一般方案 79

7.Friedberg-Muchnik定理：胜出条件 81

8.Friedberg-Muchnik定理：优先方法 82

第八章 算术分层 85

1.类Σn和Πn 85

2.Σn和Πn中的通用集 88

3.跳跃运算 89

4.分层中集的分类 94

第九章 Turing机 97

1.简单的可计算模型：需要它们做什么？ 97

2.Turing机：定义 98

3.Turing机：讨论 99

4.字问题 102

5.Turing机的模拟 103

6.Thue系统 106

7.半群、生成元和关系 108

第十章 可计算函数的算术化 111

1.有限个变量的程序 111

2.Turing机和程序 113

3.可计算函数是可算术化的 115

4.Tarski定理和Godel定理 118

5.Tarski定理和Godel定理的直接证明 120

6.算术分层和量词交换数 121

第十一章 递归函数 125

1.原始递归函数 125

2.原始递归函数的例 126

3.原始递归集 127

4.递归的其他形式 129

5.Turing机和原始递归函数 132

6.部分递归函数 133

7.Oracle可计算性 136

8.生长率的估计、Ackermann函数 138

参考文献 143

人名表 145

索引 147