《递归函数论》求取 ⇩

1．数论函数的通常定义，由n推到n+11

1.多加1，当作初等数论中最重要的方法；数论函数的定义亦可用此法而得。1

2.和、积、方冪的定义1

3.算术差n÷n2

4.可变多个项的和与可变多个因子的积3

5.m＞n，m=0，0＜m≤n的特征函数。算术上的符号函数及其相反：sg（n）与—sg（n）4

6.由多种情形“凑合”的函数5

7.“在某界限之下一切i均有……”以及“在某界限之下有一个i使得……”藉助於Σ与Π来表示6

8.算术商：[a/n]7

9.“在某界限之下最小的i使得……”藉助於Σ与Π来表示9

10.除式a/n的剩余，——res（a，n）。可整除性的特征函数9

11.因子个数，因子和。质数性的特征函数。n以下的质数的个数。9

12.差的绝对值：|a—b|.10

13.质数的种种特征10

14.质数的种种特征11

15.质数的种种特征11

16.第n个质数：p0=2；pn是第n+1个质数12

17.在n的质因子分解式中pa的方冪（指数）：expa（n）13

18.n的质因子分解式的“长度”：long（n）13

19.欧拉的〓函数14

20.min（a，b）与max（a，b）15

21.函数的最大公因子与最小公倍数。在一个定义式中有同样作用的两变元。15

22.组合论中的例。排列的个数：n！。用遞归式计算在一值位的函数值。16

23.（n/a）的定义。定义的一例，其中不参与遞归的变元并不仍旧不变17

24.斐波那奇序列的定义。不由直接的前行者出发，而由一些以前的值位推到后面的值们。18

25.由解析学所得出的数论函数。〓的遞归定义。对最近的不大的平方数的偏差：quadres（n）。平方性的特征函数：quad（n）19

26.[e·n]依照遞归而定义。20

27.由集论所得出的函数的一例：将数偶排成一列。两函数的联立定义。22

2．递归函数与递归关系24

1.遞归函数的概念及其功用。24

2.原始遞归式，原始遞归函数。26

3.与原始遞归模式稍有不同的定义。27

4.遞归关系与原始遞归关系的概念。a＞b；a=b；“a可被b整除”；“a是一质数”；“a是一平方数”都是原始遞归关系。28

5.原始遞归关系的结合。—B，即B的否定。29

6.B1与B2：B1＆B2。29

7.B1或B2：B1∨B230

8.由B1推得B2：B1→B230

9.“n以下一切i均有……”：（i）[i≤n→……]“n以下有一个i使得…”：（Ei）[i≤n…]31

10.“凑合”定义32

11.“n以下最小的或最大的i使得……”：μi[i≤n＆…]或μ′i[i≤n＆…]33

12.常用的原始遞归函数与遞归关系表35

3．串值递归式35

1.斐波那奇序列的定义的推广：一般的串值遞归式35

2.串值遞归式归约於原始遞归式与代入41

4．联立递归式41

1.把一个联立遞归式，由於把数偶排成一列而出现的，归约为串值遞归式41

2.一般联立遞归式并没有超出原始遞归函数类以外43

5．递归式，其中参数的值亦要求代入44

1.构成所定义的函数时用到的“砖石”。44

2.ψ（n，a），以这些砖石为值的，可藉串值遞归式来定义45

3.嵌套的ψ值可表成非嵌套的表示式的补助定理47

4.所定义的函数的值可由ψ（n，a）的值而得到48

5.结果的推广：这一种遞归式并没有超出原始遞归函数类以外50

6．多重递归式50

1.dv（m，n）的定义。按一变元的串值遞归式50

2.按另一变元的串值遞归式52

3.第二个串值遞归式定义的构成53

4.因第二个串值遞归式为原始遞归致第一个以及dv（m，n）亦然。54

5.一般说来，这种定义不超出原始遞归函数类以外55

7．归约55

1.把一般的代入归约为1的代入55

2.这是因为在遞归模式中包括有代入之故。它之消除，却是以再引入一个参数为代价的57

3.参数个数的减少57

4.归约到一个遞归模式，其中出现最多只有二元的函数59

5.在新模式中把代入消除；这时已经不增加变元个数60

6.消去最后的参数61

7.迄今尚未确定的补助函数ι，κ与λ的定义62

8.遞归式的归约为一个一元函数在值位0復迭式63

9.这归约的成功是以增加开始函数为代价的。我们可证明，三个开始函数已经够了，例如（A2）：n+1，a+n，quadres（n）64

10.在（A2）上n2之作成65

11.差的作成。67

12.[n/2]的作成67

13.[〓n]的作成69

14.a+n之归约於|a-n|69

15.结果：由三个开始函数出发，我们可藉代入与复迭式而作出一切原始遞归函数，多元的可仅用代入而由一元的与a+n而作成70

16.一元原始遞归函数可藉两个开始函数，不用多元函数，仅藉三个简单的模式而作出71

8．初等函数72

1.复迭式是否可以消除？由四则所定义的“初等函数”类亦包含有初等数论内扎使用的函数的大部分72

2.复迭式合增长加强，方幂的复迭式ψ（n，a）看来“优超”於一切初等函数73

3.精确地探讨：对每一个n1与n2都有一个m，使得ψ（m，a）不小於：ψ（n1，a）+ψ（n2，a）74

4.ψ（n1，a）·ψ（n2，a）76

5.ψ（n1，a）ψ(n2，a）76

6.ψ（n1，ψ（n2，a）77

7.ψ（n，a）优超於开始的初等函数78

8.当应用四则时这个性质是留传的78

9.当构成和与积时亦然79

10.方幂复迭式是原始遞归的且超出初等函数类以外80

9．非原始递归的数论函数的一例81

1.如果把方幂复迭式再行复迭，可以预期得到一个函数，优超於所有的原始遞归函数81

2.可以期望有同样性质的二元函数ψ（m，n）的定义82

3.ψ（m，n）的增长的探讨82

4.ψ（m，n）的增长的探讨83

5.ψ（m，n）的增长的探讨83

6.一元原始遞归函数是由一些开始函数出发，藉助於一些模式而构成，这便使得关于这些函数的命题可与关于自然数的命题作同样的证84

7.所有一元原始遞归函数都被ψ（m，n）所优超84

8.ψ（m，n）不可能是原始遞归85

9.所有任意多元的原始遞归函数都被ψ（m，n）所优超86

10．嵌套递归式87

1.嵌套多重（依照多元而变的遞归式超出原始遞归函数类以外；非嵌套的则否87

2.嵌套单重遞归式亦不超出原始遞归函数类以外88

3.如果把这里所描写的过程用于多重遞归式，则得一个只含一层嵌套的正规开90

4.开始值的正规化90

5.开始值的正规化91

6.就某函数而言的遞归函数的概念，多重，准确些的κ重遞归函数与其构成92

11．对角过程与多重递归式93

1.基于势而言亦必有非原始遞归函数；甚至于[τ·n]形的函数中亦有，其中τ为非负实数93

2.对无理娄τ而言[τ·n]为遞归，当而只当τ的“階乘展式”的系数an为原始遞归，在第一界限之后均有an＜n-1，这性质在证明中是有判定性的94

3.应用康托对角过程於一元原始遞归函数序列上96

4.把这些函数用函数〓（m，n）来有效地计数97

5.把这些函数用函数〓（m，n）来有效地计数98

6.函数〓（m，n）的定义是一个嵌套二重遞归式：因此再得到，后者是超出原始遞归函数类之外的99

7.同样可定义一个r+2元函数，当它的第变元适当地选择时，可等于任意一个r+1元原始遞归函数99

8.对角过程应用于κ重遞归式指出了，κ+1重遞归式是超出κ重遞归函数类以外的99

12．超穷递归式100

1.在多元函数的定义中，如果我们限于单重递归式，那将是一个很随意的限制100

2.κ元函数的值位的自然序列是一个ωk型的序列101

3.ω2型的数的序列102

4.这序列的“特征函数”的特征特性102

5.超穷递归，ω2型递归的一例103

6.一函数值由在更大的值位所取的函数值来计算的一例，用超穷递归式所定义的函数其值可在有穷次步骤内计算出105

7.ω2型的递归式可归约为一个通常的二重递归式，其中需用到，一函数可由其原始递归模式而唯一地确定107

8.ω2型的递归式可归约为一个通常的二重递归式，其中需用到，一函数可由其原始递归模式而唯一地确定109

9.反之，二重递归式可归约为一个ω2型的单重递归式110

10.自然数之依照ω3型的序列；以上过程之继续：ωk型与ωω型的序列112

11.通常κ重递归式与ωk型的超穷递归式可以彼此互相归约，多重超穷递归式可以归约为单重超穷递归式113

12.超穷递归式的特点：一元函数的定义亦可以是嵌套的；而其嵌套一般是不能解出的113

13.对三元多重递归式所用的对角过程指出了：ωω型的递归式超出多重递归函数类以外114

13．高阶递归式116

1.复迭式当作函元函数，把由从乘积出发的复迭式所得出的二重递归式分解为有函元出现的单重递归式116

2.最简单的函元函数：Vx（n，f（x））=f（n）118

3.高阶递归式与高阶递归函数119

4.所有一阶的二重递归式可分解为两个二阶的单重递归式119

5.证明的精确作出120

6.一个一阶的多重递归函数都属于二阶的单重递归函数121

7.把二阶的函数表示为一阶的多重递归函数之一例122

14．多重递归式的正规形124

1.函元函数的应用可使最复杂的嵌套递归式有一致的写法；因此现在可以处理§10所提出的多重递归式的正规形，由递归式的“成分”所构成的“代入项”124

2.以定义中的砖石为值的函数ψ的三个条件126

3.ψ的定义，其中有暂未确定的κ（n），这个ψ满足前两个条件127

4.解出嵌套式的补助定理128

5.递归性假设；如果它成立，则ψ亦满足第三条件，而且更多130

6.递归性推到底：κ（n）的定义130

7.所有多重递归式可变成一正规形，其中只有一层嵌套132

15．高阶递归式的“算术化”132

1.用高阶递归式所定义的函数ψ的值的计算132

2.计算的顺序，亦可应用于更复杂的情形134

3.在计算中所用的形式步骤的注意135

4.在计算中所用的形式步骤的注意136

5.在计算中所用的形式步骤的注意136

6.在计算中所用的形式步骤的注意137

7.在计算中所用的形式步骤的注意137

8.在计算中所用的形式步骤的注意137

9.计算永远在有穷多次步骤内结束137

10.构成一字典，其中一切所用的记号与号序列都对应于数138

11.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）139

12.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）140

13.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）142

14.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）142

15.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）142

16.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）143

17.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）144

18.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）145

19.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）146

20.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）147

21.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）147

22.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m）150

23.把一阶的定义中各步骤总结于一个数论函数r（n），从它，经过代入一个原始递归函数后我们便得到ψ150

24.r（n）的定义只是“部分”的，它亦完全不似递归的，但是用r的定义等式却能够计算ψ在任意一值位的值151

16．一般递归函数152

1.藉助于最近的、较大的平方数而作的[〓]的定义152

2.这定义不矛盾地给出函数值153

3.加入补助函数的定义等式154

4.由完全定义计算函数值；计算之步骤157

5.一般递归式与一般递归函数的概念157

17．一般递归函数的显式158

1.如果对i没有上界但具有该性质的i的确存在时，μi是一般递归的158

2.把一般递归函数表以顯式的计划，新字典161

3.一数之哥德两数163

4.把在计算中所允许的代入分解为基本步骤163

5.基本的归约代入步骤的哥德两数164

6.其它的归约步骤与其结果的哥德两数165

7.归约结果的总结166

8.推演的哥德函数的特征166

9.值〓（a1，…，ar）的哥德两数167

10.顯式168

11.一般递归函数由开始原始递归函数与两个运算而构成，所得的顯式是全能的169

12.顯式的种种形式170

18．显式再行简约的可能性177

1.一般递归函数〓可以变成一个更简约的顯式（不用ψ）的条件是〓（a1，…，ar）=m的原始递归性177

2.非原始递归函数之一例，对它来说，这关系是原始递归的178

3.这里出现一种递归式，其函数值不是由确定多个而是由可变多个以前的两数值而构成的180

4.一般递归函数之一例，对它来说，这关系是非原始递归的183

5.其它有关的结果184

6.马尔科夫的证明，并不是所有一般递归函数都可以写成更简的顯式，“广延”函数185

7.“全能”ψ函数的概念，全能性的必要条件186

8.补助定理，用以证明这条件亦是充分的188

9.马乐科夫命题的证明，即“广延”函数ψ，对每一种变元个数来说，都是“全能”的189

19．非一般递归函数之一例190

1.顯式可使对角过程能应用于一般递归函数190

2.对角函数能够在某一个更一般的意义上是递归的或者根本是可计算的么？192

20．可计算函数192

1.一计算，可重复且可信托于他人的，只能是机械的，用以演出计算的机器的想法192

2.机器的记号与布局，它活动的基本动作；函数值〓（0），〓（1），〓（2），…出现于纸片上194

3.计算〓（n）=1的机器195

4.计算〓（n）=n+1机器196

5.计算〓（n）=n+1机器198

6.杜令机器可以计算第一个一般递归函数，但亦可计算有效给出的实数200

7.如果杜令机器计算一个数论函数〓（n）的值，则它活动的基本动作以及它环境的情况可用原始递归函数来描述201

8.如果杜令机器计算一个数论函数〓（n）的值，则它活动的基本动作以及它环境的情况可用原始递归函数来描述202

9.如果杜令机器计算一个数论函数〓（n）的值，则它活动的基本动作以及它环境的情况可用原始递归函数来描述203

10.如果杜令机器计算一个数论函数〓（n）的值，则它活动的基本动作以及它环境的情况可用原始递归函数来描述205

11.从写0的情况起到第n个情况止，所写1的个数亦是n的原始递归函数205

12.如果这机器在第ξ（n）情况下写第n+1个0，则ξ（n）是一般递归的；因此得出由机器所计算的函数的一般递归性206

13.因此很可以提出，一般递归函数是在最一般的意义上可计算的数论函数207

21．历史与应用207

1.递归函数的历史是与数学基础探讨的历史有密切关联的207

2.递归数论无须用到无穷集来构成208

3.证明论的计划；递归数论在无数学上的可用性208

4.希尔伯说对证明连续统假设的计划；用永远“更高”类的递归式来作出数论函数209

5.哥德尔命题，用所讨论的系统的工具不能证明不矛盾性；算术化方法209

6.在数化系统内不能塑述的一个方法：超穷递归式211

7.最一般的可计算函数与一般递归函数之等同，应用211

8.在概率论上212

9.在直觉主义逻辑上213

10.在递归函数部门上的一例表明了：为什么直觉主义的慎重是必要的214

11.在集论上217

12.在特征超穷序数上218

13.在证明某些问题的不能有效判定上（例如，判定问题，半羣的“字的问题”）219

22．以下问题是不能有效判定的：那一个等式系定义一个一般递归函数221

1.定义一般递归函数的自然数（因而可代替定义等式系）221

2.这些数是不能有效计数的223

3.我们不能有效判定，那一个数定义一般递归函数224

23．算术问题的可一般判定性的问题225

1.算术式，哥尔德巴哈臆测的算术式225

2.恒等式y=ax与某一序列的存在是同意义的，任意一个有穷项的序列可当作一数被一等差级数各项除后的剩余来处理225

3.y=ax因此可变成算术式227

4.所有原始递归关系是算术的228

5.所有一般递归关系是算术的229

6.相反方向的归约亦是可以的：量词的总括230

7.不可能给出一个有效的一般过程来判定甚至只含一个自由变元的算术问题230

24．递归性概念的推广．在解析学上的应用231

1.对应于一误差限的高积数当作递归函数，有效的收敛，递归的收敛，递归的有理数序列，递归实数231

2.给出一个单调的、有界的原始递归有理数序列，其中用到一个原始递归函数ρ（m，n），而且μx[ρ（m，x）=0]为非一般递归233

3.这个序列不能有效收敛234

4.并非所有递归实数都有一个递归小数展式，有递归阶乘展式的实数确定一个递归分划235

5.如果一数确定递归分划，则它可展成一系列有递归系数的级数237

6.在这些级数中亦包括了小数与阶乘展式239

7.如果递归实数r是“递归无理”的，则它决定一递归分划240

8.在这部门上的其它探讨243

附录递归证法的若干形式244

参考文献249

中德译名对照表256

德中译名对照表257

人名对照表258