可计算函数讲义PDF电子书下载

目 录 1

§1．引言 1

§2．集合与函数理论方面的一些预备知识 9

1．集合 9

2．函数 13

3．代入 16

4．部分映象 21

5．广延函数 25

6．特征函数 27

7．原始递归 29

8．可计算函数的例 32

§ 3．数理逻辑方面的预备知识 34

1．命题和命题形式 34

2．真假值 40

3．谓词及其运算 43

4．受囿的量词 54

5．最小数”算子 58

6．受囿的“最小数”算子 60

7．受囿的“最大数”算子 61

9．直观可计算谓词 62

8．受囿的“算个数”算子 62

§4．原始递归的函数、集合与谓词 66

1．原始递归函数 67

2．原始递归集合 73

3．原始递归谓词 80

4．原始递归函数（续完） 86

5．N与N8之间的原始递归对应 91

6．集合N∞的原始递归枚举函数 96

1．递归可枚举集合 105

§5．递归可枚举的集合与谓词 105

2．递归可枚举谓词 116

§6．部分递归函数 120

1．定义和基本假设 121

2．具有递归可枚举图形的函数 125

3．图形定理的推论 132

§7．一般递归的函数、集合与谓词 139

1．一般递归的函数与集合 139

2．一般递归谓词 144

3．一般递归的枚举函数 146

1．辅助工具 151

§8．原始递归函数的通用函数 151

2．通用函数 161

3．重要例子 193

§9．部分递归函数的通用函数和递归可枚举集合的通用集合 202

1．通用函数 202

2．重要例子 207

3．通用集合．通用序偶 216

§10．关于递归可枚举集合的补充知识 226

1．可单值化性 227

2．可分隔性和不可分隔性 230

3．单纯集 235

§11．编号和运算 241

1．编号和已编号集合 241

2．系统？(s)和P(8)的编号 244

3．构造性算子 264

§12．可计算函数论在数学分析中的应用：分出可计算实数 276

1．实数 277

（i）康托理论 277

（ii）狄德金理论 278

（iv）q进制理论 279

（iii）区间理论 279

2．有理数的可计算函数 281

3．可计算实数 286

（ i）康托意义下可计算的数 286

（ii）狄德金意义下可计算的数 289

（iii）区间意义下可计算的数 292

（iv）十进制可计算的数；q进制可计算的数 294

（v）构造性连续统 297

4．可计算实数的表示系统 297

§13．可计算函数论在逻辑学中的应用：否定定义的构造化 314

1．构造性的非有穷性 315

2．构造性的不可枚举性 321

3．构造性的不可分隔性 327

§14．可计算函数论在计算数学中的应用：抽象计算机的可能性 333

1．Ⅰ型机器 333

2．Ⅱ型机器 338

3．多带机器 346

4．在机器上可计算的函数 354

5．定理3和4的证明 395

参考文献 400

名词索引 405