查看“︁原始递归函数”︁的源代码

{{Rough translation|time=2024-05-24T02:50:00+00:00}}
{{NoteTA
|G1 = IT
|G2 = Math
}}
在[[可计算性理论]]中，'''原始递归函数'''（{{lang-en|primitive recursive functions}}）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用[[递归]]和[[函数复合|复合]]作为中心运算来定义，并且是[[递归函数]]的严格的[[子集]]，它们完全是[[可计算函数]]。通过补充允许[[偏函数]]和介入无界查找运算可以定义出递归函数的更广泛的类。

通常在[[数论]]中研究的很多函数，近似于实数值函数，比如[[加法]]、[[除法]]、[[阶乘]]、[[冪運算|指数]]，找到第 ''n'' 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始递归的函数，尽管某些函数是已知的(比如[[阿克曼函数]])。所以，通过研究它们，我们能发现有广泛影响的结论的那些性质。

原始递归函数可以用总是停机的[[图灵机]]计算，而递归函数需要[[图灵完全]]系统。

原始递归函数的集合在[[计算复杂性理论]]中叫做[[PR (複雜度)|PR]]。

== 定义 ==

原始递归函数接受[[自然数]]或自然数的[[元组]]作为参数并生成自然数。接受 ''n'' 个参数的函数叫做 ''n''-[[元数|元]]函数。基本原始递归函数用如下[[公理]]给出:

#'''常数函数''': 0 元[[常数函数]] 0 是原始递归的。
#'''后继函数''': 1 元[[后继函数]] ''S''，它接受一个参数并返回[[皮亚诺公理]]给出的后继数，是原始递归的。
#'''投影函数''':  对于所有 ''n''≥1 和每个 1≤''i''≤''n'' 的 ''i''，''n'' 元投影函数 ''P''<sub>''i''</sub><sup>''n''</sup>，它接受 ''n'' 个参数并返回它们中的第 ''i'' 个参数，是原始递归的。

更加复杂的递归函数可以通过应用下列公理给出的[[运算]]来获得:

#'''复合''': 给定''k'' 元原始递归函数 ''f''，和 ''k'' 个 ''m'' 元原始递归函数 ''g''<sub>1</sub>,...,''g''<sub>''k''</sub>，''f'' 和 ''g''<sub>1</sub>,...,''g''<sub>''k''</sub> 的[[函数复合|复合]]，也就是 ''m'' 元函数 ''h''(''x''<sub>1</sub>,...,''x''<sub>''m''</sub>) = ''f''(''g''<sub>1</sub>(''x''<sub>1</sub>,...,''x''<sub>''m''</sub>),...,''g''<sub>''k''</sub>(''x''<sub>1</sub>,...,''x''<sub>''m''</sub>)), 是原始递归的。
#'''原始递归''': 给定 ''k'' 元原始递归函数 ''f''，和 ''k''+2 元原始递归函数 ''g''，定义为 ''f'' 和  ''g'' 的原始递归的 ''k''+1 元函数，也就是函数 ''h'' 这里的 ''h''(0,''x''<sub>1</sub>,...,''x''<sub>''k''</sub>) = ''f''(''x''<sub>1</sub>,...,''x''<sub>''k''</sub>) 并且 ''h''(''S''(''n''),''x''<sub>1</sub>,...,''x''<sub>''k''</sub>) = ''g''(''h''(''n'',''x''<sub>1</sub>,...,''x''<sub>''k''</sub>),''n'',''x''<sub>1</sub>,...,''x''<sub>''k''</sub>), 是原始递归的。

服从这些公理的函数是原始递归的，如果它是上述基本函数之一，或者它可以通过应用有限次数的运算获得自基本函数。

=== 投影函数的作用 ===
投影函数可用来避免采用上述明显刻板的函数[[元数]]方式；通过使用各种投影函数的复合，有可能把一个函数的参数子集传递到另一个函数。例如，如果 ''g'' 和 ''h'' 是二元原始递归函数，则
:<math>f(a,b,c) = g(h(a,c),h(a,b)) \!</math>
也是原始递归的。使用投影函数的一个形式定义为
:<math>f(a,b,c) = g(h(P^3_1(a,b,c),P^3_3(a,b,c)),h(P^3_1(a,b,c),P^3_2(a,b,c)))</math>.

=== 转换谓词到数值函数 ===

在某些设置中，自然的考虑接受混合了数值和真值{ t= true, f=false } 的参数，或生成真值作为输出的原始递归函数(参见 Kleene [1952 pp.226-227])。这可以通过把真值识别为任何固定方式的数值来完成。例如，通常把真值''t'' 识别为 ''1'' 和真值 ''f'' 识别为 ''0''。一旦作出这种识别，集合 ''A'' 的[[指示函数|特征函数]]，它在文字上返回 ''1'' 或 ''0''，可以被看作判定一个数是否在集合 ''A'' 中的谓词。把谓词识别为数值函数的这种方式将假定于本文余下部分。

== 例子 ==

===[[加法]]===

直觉上我们会把加法递归的定义为:

:add(0,''x'')=''x''
:add(''n''+1,''x'')=add(''n'',''x'')+1

为了使它适合于严格的原始递归定义,我们定义:

:add(0,''x'')=''P''<sub>1</sub><sup>1</sup>(''x'')   
:add(S(''n''),''x'')=''S''(''P''<sub>1</sub><sup>3</sup>(add(''n'',''x''),''n'',''x''))
(注意: 这里的 ''P''<sub>1</sub><sup>3</sup> 是一个函数，它接受 3 个参数并返回第一个。)

''P''<sub>1</sub><sup>1</sup> 是简单的[[恒等函数]]；包含它是上述原始递归运算定义的要求；它扮演了 ''f'' 的角色。''S'' 和 ''P''<sub>1</sub><sup>3</sup> 的复合，它是原始递归的，它扮演了 ''g'' 的角色。

===[[减法]]===

我们可以定义''有限减法''，就是说，截止到 0 的减法(因为我们还没有负数的概念呢)。首先我们必须定义"前驱" 函数，它担任后继函数的对立物。

直觉上我们会把前驱定义为:

:pred(0)=0
:pred(''n''+1)=''n''

为了使它适合正式的原始递归定义，我们写:

:pred(0)=0
:pred(S(''n''))=''P''<sub>2</sub><sup>2</sup>(pred(''n''),''n'')

现在我们以类似加法的方式定义减法。

:sub(0,''x'')=''P''<sub>1</sub><sup>1</sup>(''x'')
:sub(S(''n''),''x'')=pred(''P''<sub>1</sub><sup>3</sup>(sub(''n'',''x''),''n'',''x''))

出于简单的缘故，切换了"标准"定义的参数次序来适合原始递归的要求，就是说， sub(''a'',''b'') 对应于 ''b''-''a''。这可以轻易的使用适当的投影来矫正。

很多类似的函数可以被证明是原始递归的；一些例子包括[[条件]]、[[冪運算|指数]]、[[素数检验]]和[[数学归纳法]]，并且原始递归函数可以被扩展来运算在其他对象上比如整数和有理数。

==== 在整数和有理数上的运算 ====

通过使用[[哥德尔数]]，原始递归函数可以被扩展到在其他对象比如整数和[[有理数]]上的运算上。如果以标准方式编码整数用哥德尔数，算术运算包括加法、减法、乘法都是原始递归的。类似的，如果以哥德尔数表示有理数，则[[域 (数学)|域]]运算都是原始递归的。

== 与递归函数的联-{}-系 ==

通过介入[[mu算子|无界查找算子]]可定义更广泛的[[偏递归函数]]类。这个算子的使用可以导致[[偏函数]]，就是说，对每个参数有最多一个值，但是不同于全函数，不必须对参数有值的关系(参见[[定义域]])。一个等价的定义声称偏递归函数是可以被[[图灵机]]就算的函数。全递归函数是对所有输入有定义的偏递归函数。

所有原始递归函数都是全递归的，但不是所有全递归函数都是原始递归的。[[阿克曼函数]] ''A''(''m'',''n'')是周知的不是原始递归的全递归函数。原始递归函数有作为使用阿克曼函数的全递归函数的子集的一个特征。这个特征声称一个函数是原始递归的，当且仅当有一个自然数 ''m'' 使得这个函数可以被总在 A(''m'',''n'') 或更少步骤内停机的图灵机计算，这里的 ''n'' 是原始递归函数的参数的总数。

== 限制 ==

原始递归函数意图紧密对应于我们直觉上可计算函数应该的样子。当然函数的初始集合在直觉上是可计算的(因为它们非常简单)，而你能用来建立新原始递归函数的两个运算也是非常直接的。但是原始递归函数的集合不包含所有可能的可计算函数 — 这可以看作康托尔[[对角论证法]]的变体。这个论证提供了一个不是原始递归的可计算函数。证明的梗概如下:

原始递归函数集合可以[[递归可枚举集合|被计算枚举]]。这个编号方案在函数定义上是唯一的，尽管在实际函数自身上不是唯一的(因为所有的函数都可以有无限数目的定义 — 考虑简单的由[[恒等函数]]构成)。这个编码在可计算性的形式模型，比如[[递归函数]]或[[图灵机]]下定义的意义上是可计算的，[[邱奇-图灵论题]]涉及的任何机器都可以。

现在考虑一个矩阵，这里的行是在这个编号方案下的有一个参数的原始递归函数，而列是自然数。则每个元素 (''i'', ''j'') 对应于计算于数 ''j'' 之上的第 ''i'' 个一元原始递归函数。我们可以写为 ''f''<sub>''i''</sub>(''j'')。

现在我们考虑函数 ''g''(''x'') = S(''f''<sub>''x''</sub>(''x''))。''g'' 位于这个矩阵的对角线上，并简单的对它找到的值加一。这个函数是可计算的(按上述定义)，但是明显的没有计算它的原始递归函数存在，因为它与每个可能的原始递归函数都有至少一个值不同。所以，必然存在不是原始递归的可计算函数。

这个论证可以应用于能用这种方式枚举的任何一类的可计算(全)函数上。所以，任何这种可计算(全)函数的明确列表都不可能是完全的，比如那些可以用[[判定器]]计算的函数。但是要注意，''偏''可计算函数集合(那些不需要对所有参数有定义的函数)可以被明确的枚举，例如通过枚举[[图灵机]]编码。

可以明确展示的一个简单的 1-元可计算函数[[阿克曼函數]]，它是对任何自然数递归定义的，但不是原始递归的。

== 历史 ==
[[递归定义]]以前在数学中或多或少地被正式使用过，但原始递归的构造可以追溯到[[理查德·戴德金]]的 "Was sind und was sollen die Zahlen? (1888). 这项工作是第一个给出某个递归结构定义了一个唯一函数的证明。 <ref name="Smith2013">{{cite book|author=Peter Smith|title=哥德尔定理简介|year=2013|publisher=剑桥大学出版社|isbn=978-1-107-02284-3|pages=98-99|edition=2nd}}</ref><ref name="Tourlakis2003">{{cite book|author=George Tourlakis|title=Lectures in Logic and Set Theory: Volume 1, Mathematical Logic|year=2003|publisher=Cambridge University Press|isbn=978-1-139-43942-8|page=129}}</ref><ref name="Downey2014">{{cite book|editor=Rod Downey|title=图灵的遗产。来自图灵逻辑思想的发展|year=2014|url=https://archive.org/details/isbn_9781107043480|publisher=剑桥大学出版社|isbn=978-1-107-04348-0|page=[https://archive.org/details/isbn_9781107043480/page/474 474]}}</ref>

原始递归算术是由[[Thoralf Skolem]]首次提出的<ref>[[Thoralf Skolem]] 。(1923) "The foundations of elementary arithmetic" in [[Jean van Heijenoort]], translator and ed. (1967) ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931''。Harvard Univ. Press: 302-33.</ref> 1923年。

目前的术语是由[[Rózsa Péter]]（1934年）在[[Wilkinson]]之后创造的。(1934)在[[威廉·阿克曼|阿克曼]]于1928年证明了今天以他名字命名的函数不是原始递归函数之后，这一事件促使人们需要重新命名在那之前被简单称为递归函数的东西。

==参见==
* [[遞歸 (電腦科學)]]
* [[双重递归]]
* [[原始递归集函数]]
* [[原始递归序数函数]]

==注释==
{{reflist}}

== 参考文献 ==
* Brainerd, W.S., Landweber, L.H. (1974), ''Theory of Computation'', Wiley, {{isbn|0-471-09585-0}}.
* [[Robert I. Soare]], ''Recursively Enumerable Sets and Degrees'' , Springer-Verlag, 1987.  {{isbn|0-387-15299-7}}
* [[Stephen Kleene]] (1952) ''Introduction to Metamathematics'', North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint). In Chapter XI. General Recursive Functions §57
* [[George Boolos]], [[John P. Burgess|John Burgess]], [[Richard Jeffrey]] (2002), ''Computability and Logic: Fourth Edition'', Cambridge University Press, Cambridge, UK. Cf pp. 70-71.
* Robert I. Soare 1995 ''Computability and Recursion'' http://www.people.cs.uchicago.edu/~soare/History/compute.pdf {{Wayback|url=http://www.people.cs.uchicago.edu/~soare/History/compute.pdf |date=20220331221004 }}
* Daniel Severin 2008, ''Unary primitive recursive functions'', J. Symbolic Logic Volume 73, Issue 4, pp.&nbsp; 1122-1138 [https://arxiv.org/abs/cs/0603063v3 arXiv] {{Wayback|url=https://arxiv.org/abs/cs/0603063v3 |date=20220310135015 }} [http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.jsl/1230396909 projecteuclid] {{Wayback|url=http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.jsl%2F1230396909 |date=20171204061321 }}

{{数学逻辑}}

[[Category:递归论]]
[[Category:函数]]
[[Category:递归]]