原始递归函数

数学术语

在可计算性理论中，原始递归函数对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们是完全可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。

简介

在可计算性理论中，原始递归函数（英语：primitive recursive functions）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。

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

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

原始递归函数的集合在计算复杂性理论中叫做PR。

介绍

合成

设 f 是 k 元部分函数，g1、g2、...、gk是 k 个n 元部分函数，令

h(x1,...,xn)=f(g1(x1,...,xn),...,gk(x1,...,xn))

称函数h是由 f 和g1,...,gk 合成得到的。

原始递归

1. 设 g 是2元全函数，k 是一个常数，函数 h 由下述等式给出

h(0)=k,

h(t+1)=g(t,h(t))

称 h 是由 g 经过原始递归运算得到的。

2. 设 f 和 g 分别是 n 元和 n+2 元全函数， n+1 元函数 h 由下述等式给出

h(x1,...,xn,0)=f(x1,...,xn),

h(x1,...,xn,t+1)=g(t,h(x1,...,xn,t),x1,...,xn)

称 h 是由 f 和 g 经过原始递归运算得到的。

定义

初始函数

包括：

后继函数： s(x)=x+1

零函数： n(x)=0

投影函数： Ui n (x1,...,xn)=xi, 1≦i≦n

定义：

由初始函数经过有限次合成和原始递归得到的函数称作原始递归函数

常用

1. 常数K

2. x

3. x+y

4. x·y

5. x!

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

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

原始递归函数的集合在计算复杂性理论中叫做 PR 。

与递归函数的联系

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

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

限制

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

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

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

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

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

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

全国各地天气预报查询

上海市

市辖区

云南省

临沧市

云南省

丽江市