《可计算函数讲义》

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