在数理逻辑和计算机科学中,递归函数μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关,而且递归函数的归纳定义(见下)创建在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。

其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。

所有递归函数的集合叫做R。

定义

μ-递归函数(或偏μ-递归函数)是接受自然数的有限元组并并返回一个单一自然数的偏函数。它们是包括初始函数并闭合在复合、原始递归和μ算子下的最小的偏函数类。

包括初始函数并闭合在复合和原始递归下的(就是说使用前五个函数定义的)最小的函数类是原始递归函数类。所有原始递归函数都是全函数。需要第六个或"μ算子"是因为不是所有全函数都可以只用五个原始递归函数来计算(比如阿克曼函数)。在这些实例中μ算子终止运算。它充当无界查找算子,无界但仍然(通过全函数定义)被某种方式(比如归纳证明)证明为最终生成一个数并终止运算。

但是,如果无界μ算子自身是偏函数 -- 就是说存在某个数它不能为其返回一个数 -- 使用它的函数将也是偏函数 -- 对某些数没有定义。在这些实例中,因为它是无界的,μ算子将永远查找,永不通过生成一个数而终止运算。(某些算法可以采用可以生成指示“不可判定”的符号"u"并以此终止运算的u-算子(cf Kleene(1952)pp. 328ff))。换句话说:使用偏μ算子的偏μ-递归函数可能不是全函数。全μ-递归函数的集合是全函数的偏μ-递归函数的子集。

前三个函数叫做"初始"或"基本"函数:(Kleene (1952) p. 219):

  • (1)常数函数:对于每个自然数n和所有的k:
f ( x 1 , , x k ) = n {\displaystyle f(x_{1},\ldots ,x_{k})=n}
有时这个常数通过重复使用后继函数和叫做"初始对象0(零)"的对象来生成(Kleene (1952) p.?)
  • (2)后继函数S: "从已经生成的对象到另一个对象n+1或n'(n后继者)"(ibid)。
S(x) ≡def f(x) = x' = x +1
  • (3)投影函数Pi(也叫做恒等函数Ii):对于所有自然数i使得 1 i k {\displaystyle 1\leq i\leq k} :
Pi ( x 1 , , x k ) {\displaystyle (x_{1},\ldots ,x_{k})} =def f ( x 1 , , x k ) = x i {\displaystyle f(x_{1},\ldots ,x_{k})=x_{i}} .
f ( x 1 , , x k ) = h ( g 1 ( x 1 , , x k ) , , g m ( x 1 , , x k ) ) {\displaystyle f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))} 的一个函数。
f ( 0 , x 1 , , x k ) = g ( x 1 , , x k ) {\displaystyle f(0,x_{1},\ldots ,x_{k})=g(x_{1},\ldots ,x_{k})} ,
f ( y + 1 , x 1 , , x k ) = h ( y , f ( y , x 1 , , x k ) , x 1 , , x k ) {\displaystyle f(y+1,x_{1},\ldots ,x_{k})=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}
在任何一个情况下:这个函数μy f返回最小的自然数 y {\displaystyle y} 使得,如果这样的y存在,则f(0,x1,x2,...,xk), f(1,x1,x2,...,xk), ..., f(y,x1,x2,...,xk)都是有定义的,并且f(y,x1,x2,...,xk) = 0;如果这样的y不存在,则μy f是对特定参数x1,...,xk是未定义的。

强等于算子 {\displaystyle \simeq } 被用来比较偏μ-递归函数。这是对所有偏函数fg定义的所以

f ( x 1 , , x k ) g ( x 1 , , x l ) {\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}

成立,当且仅当对于参数的任何选择要么两个函数都有定义并且它们的值相等要么两个函数都是未定义的。

同其他模型的等价性

在可计算性模型的等价中在对特定输入不终止的图灵机和对这个输入得到未定义结果的相应偏递归函数之间是平行/并列的。无界查找运算是不能通过原始递归的规则定义的,因为它们不提供"无限循环"(未定义值)的机制。

范式定理

范式定理源于Kleene声称对于每个k有原始递归函数 U ( y ) {\displaystyle U(y)\!} T ( y , e , x 1 , , x k ) {\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!} 使得对于任何k个自由变量的μ-递归函数 f ( x 1 , , x k ) {\displaystyle f(x_{1},\ldots ,x_{k})\!} 有一个e使得

f ( x 1 , , x k ) U ( μ y T ( y , e , x 1 , , x k ) ) {\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))}

e被叫做函数f索引哥德尔数。这个结果的一个结论是任何μ-递归函数都可以使用把μ算子应用于(全)原始递归函数的一个单一实例来定义。

Minsky (1967)(同样Boolos-Burgess-Jeffrey (2002) pp. 94-95)观察到上面定义的U在本质上是通用图灵机的μ-递归等价物:

“要构造U就是写下通用递归函数U(n, x)的定义,它正确的解释数n并计算x的适当的函数。要直接构造U涉及与我们在构造通用图灵机的研究中本质上同量的努力,和本质上同样的想法”(italics in original, Minsky (1967) p. 189)。

例子

139001.net
问题反馈联系QQ:1215,也可发qq邮箱