递归函数

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

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

所有递归函数的集合叫做 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) 投影函数 P_i^k (也叫做恒等函数 I_i^k ): 对于所有自然数 i 使得 $1 \le i \le k$ :

P_i^k $(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)$ 对每个 i 有 $1 \le i \leq m$ ，并返回映射 x₁, ... x_k 到

$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)$ ，它的参数是 x₁ , . . ., x_k。这个函数 $f$ 要么是从自然数 { 0, 1, ... n } 到自然数 { 0, 1, ... n } 的数论函数，要么是运算于谓词(输出 { t, f })上生成 { 0, 1 } 的表示函数。

在任何一个情况下: 这个函数 μy f 返回最小的自然数

y

使得，如果这样的 y 存在，则 f(0,x₁,x₂,...,x_k), f(1,x₁,x₂,...,x_k), ..., f(y,x₁,x₂,...,x_k) 都是有定义的，并且 f(y,x₁,x₂,...,x_k) = 0；如果这样的 y 不存在，则 μy f 是对特定参数 x₁,...,x_k 是未定义的。

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

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

例子

斐波那契数列
McCarthy 91 函数

参见

外部链接

Stanford Encyclopedia of Philosophy entry

引用

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.

George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70-71.

2个分类: 递归论 | 函数

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History

递归函数

目录

定义

同其他模型的等价性

范式定理

例子

参见

外部链接

引用