《递归函数论》

绪论1

1 自然数集与数论函数1

2 函数与依变元4

3 可直接定义的函数9

4 迭置11

5 算子18

6 函数的定义过程(组成过程)26

7 谓词与特征函数30

8 数学归纳法37

第一章 五则函数43

1 五则函数(上)43

2 五则函数(下)49

3 配对函数52

4 有限数列的表示59

5 迭置的化归63

第二章 算子72

1 摹状算子与求逆算子72

2 递归算子78

3 算子的分类86

4 算子的相互表示及化归90

5 递归生成的函数集101

6 三大函数集108

第三章 初等函数集110

1 四个初等函数集(上)110

2 四个初等函数集(下)116

3 初等函数集的一些重要性质124

4 最强的初等算子128

5 初基函数集133

第四章 原始递归函数140

1 与初等函数的关系140

2 原始递归式的化归142

3 原始递归式的加强153

4 多重递归式166

5 非原始递归函数之一例181

6 递归式与数学归纳法185

第五章 一般递归函数187

1 一般递归函数与原始递归函数187

2 一般递归式的化归190

3 一般递归式的加强194

4 一般递归式与超穷递归式197

5 摹状式与一般递归式203

6 利用摹状式以作一般递归函数集208

7 一般递归函数的典范式214

8 部分函数与半递归函数224

9 可在有限步骤内计算的函数229

10 可形式计算的函数239

第六章 递归生成的函数集246

1 控制函数246

2 递归生成函数集的枚举250

3 一般递归函数集的枚举256

4 自身枚举与主要自身枚举261

第七章 谓词与集合265

1 各种谓词265

2 多项式谓词266

3 新初基谓词269

4 半递归谓词273

5 算术谓词280

6 非算术谓词之一例288

7 部分函数与半特征函数290

8 集合293

第八章 判定问题298

1 个别问题与大量问题298

2 判定性的初步性质302

3 基本的不能判定问题304

4 半递归函数间的关系和性质之不可完全判定性307