递归函数

维基百科,自由的百科全书
跳转至: 导航搜索

数理逻辑计算机科学中,递归函数μ-递归函数是一类从自然数自然数函数,它是在某种直觉意义上是"可计算的"。事实上,在可计算性理论中证明了递归函数精确的是图灵机可计算函数递归函数有关于原始递归函数,并且它们的归纳定义(见下)建造在原始递归函数之上。但是,不是所有递归函数都是原始递归函数—最著名的这种函数是阿克曼函数

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

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

定义[编辑]

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

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

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

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

  • (1)常数函数:对于每个自然数n和所有的k:
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)投影函数Pik(也叫做恒等函数Iik):对于所有自然数i使得1 \le i \le k:
Pik(x_1,\ldots,x_k) =def f(x_1,\ldots,x_k) = x_i.
  • (4)复合算子:复合也叫做代换,接受一个函数h(x_1,\ldots,x_m)和函数g_i(x_1,\ldots,x_k)对每个i1 \le i \leq m,并返回映射x1, ... xk
f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))的一个函数。
  • (5)原始递归算子:接受函数g(x_1,\ldots,x_k)h(y,z,x_1,\ldots,x_k)并返回唯一的函数f使得
f(0,x_1,\ldots,x_k) = g(x_1,\ldots,x_k),
f(y+1,x_1,\ldots,x_k) = h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k)
  • (6)μ算子:μ算子接受一个函数f(y,x_1,\ldots, x_k)并返回函数\mu y f(y,x_1,\ldots,x_k),它的参数是x1 , . . ., xk。这个函数f要么是从自然数{ 0, 1, ... n }到自然数{ 0, 1, ... n }的数论函数,要么是运算于谓词(输出{ t, f })上生成{ 0, 1 }的表示函数
在任何一个情况下:这个函数μy f返回最小的自然数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是未定义的。

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

f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l)

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

同其他模型的等价性[编辑]

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

范式定理[编辑]

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

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)。

例子[编辑]

参见[编辑]

外部链接[编辑]

引用[编辑]

  • Stephen Kleene(1952)Introduction to Metamathematics. Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971); Tenth impression 1991, ISBN 0-7204-2103-9.
  • Soare, R. Recursively enumerable sets and degrees. Springer-Verlag 1987.
  • Marvin L. Minsky(1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.
On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.