遞歸函數

在數理邏輯和電腦科學中，**遞迴函式**或 **μ- 遞迴函式**是一類從自然數到自然數的函式。直覺上遞迴函式是 "可計算的"。事實上在可計算性理論中已經證明了它確實是圖靈機的可計算函式。遞迴函式與原始遞迴函式相關，而且遞迴函式的歸納定義（見下）建立在原始遞迴函式之上。但不是所有遞迴函式都是原始遞迴函式 —— 其中最著名的是阿克曼函式。

其他等價的函式類是 λ- 遞迴函式和馬爾可夫演算法可計算的函式。

所有遞迴函式的集合叫做 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\leq i\leq 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})$ 對每個 _i_ 有 $1\leq i\leq m$ ，並返回對映 _x_1, ... _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 yf(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,_x_1,_x_2,...,_x_k), _f_(1,_x_1,_x_2,...,_x_k), ..., _f_(_y_,_x_1,_x_2,...,_x_k) 都是有定義的，並且 _f_(_y_,_x_1,_x_2,...,_x_k) = 0；如果這樣的 _y_ 不存在，則 μ_y_ _f_ 是對特定參數 _x_1,...,_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.