遞歸函數

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

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

所有遞歸函數的集合叫做R。

定義

μ-遞歸函數（或偏μ-遞歸函數）是接受自然數的有限元組並並返回一個單一自然數的偏函數。它們是包括初始函數並閉合在複合、原始遞歸和μ算子下的最小的偏函數類。

包括初始函數並閉合在複合和原始遞歸下的（就是說使用前五個函數定義的）最小的函數類是原始遞歸函數類。所有原始遞歸函數都是全函數。需要第六個或"μ算子"是因為不是所有全函數都可以只用五個原始遞歸函數來計算（比如阿克曼函數）。在這些實例中μ算子終止運算。它充當無界尋找算子，無界但仍然（通過全函數定義）被某種方式（比如歸納證明）證明為最終生成一個數並終止運算。

但是，如果無界μ算子自身是偏函數 -- 就是說存在某個數它不能為其返回一個數 -- 使用它的函數將也是偏函數 -- 對某些數沒有定義。在這些實例中，因為它是無界的，μ算子將永遠尋找，永不通過生成一個數而終止運算。（某些演算法可以採用可以生成指示「不可判定」的符號"u"並以此終止運算的u-算子（cf Kleene（1952）pp. 328ff））。換句話說：使用偏μ算子的偏μ-遞歸函數可能不是全函數。全μ-遞歸函數的集合是全函數的偏μ-遞歸函數的子集。

前三個函數叫做"初始"或"基本"函數：（Kleene (1952) p. 219）：

• （1）常數函數：對於每個自然數n和所有的k:

${\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）投影函數P_i^k（也叫做恆等函數I_i^k）:對於所有自然數i使得${\displaystyle 1\leq i\leq k}$:

P_i^k${\displaystyle (x_{1},\ldots ,x_{k})}$ =_def ${\displaystyle f(x_{1},\ldots ,x_{k})=x_{i}}$.

• （4）複合算子：複合也叫做代換，接受一個函數${\displaystyle h(x_{1},\ldots ,x_{m})}$和函數${\displaystyle g_{i}(x_{1},\ldots ,x_{k})}$對每個i有${\displaystyle 1\leq i\leq m}$，並返回對映x₁, ... 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}))}$的一個函數。

• （5）原始遞歸算子：接受函數${\displaystyle g(x_{1},\ldots ,x_{k})}$和${\displaystyle h(y,z,x_{1},\ldots ,x_{k})}$並返回唯一的函數${\displaystyle f}$使得

${\displaystyle f(0,x_{1},\ldots ,x_{k})=g(x_{1},\ldots ,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})}$。

• （6）μ算子：μ算子接受一個函數${\displaystyle f(y,x_{1},\ldots ,x_{k})}$並返回函數${\displaystyle \mu yf(y,x_{1},\ldots ,x_{k})}$，它的參數是x₁ , . . ., x_k。這個函數${\displaystyle f}$要麼是從自然數{ 0, 1, ... n }到自然數{ 0, 1, ... n }的數論函數，要麼是運算於謂詞(輸出{ t, f })上生成{ 0, 1 }的表示函數。

在任何一個情況下：這個函數μy f返回最小的自然數${\displaystyle 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是未定義的。

強等於算子${\displaystyle \simeq }$被用來比較偏μ-遞歸函數。這是對所有偏函數f和g定義的所以

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

成立，若且唯若對於參數的任何選擇要麼兩個函數都有定義並且它們的值相等要麼兩個函數都是未定義的。

同其他模型的等價性

在可計算性模型的等價中在對特定輸入不終止的圖靈機和對這個輸入得到未定義結果的相應偏遞歸函數之間是平行/並列的。無界尋找運算是不能通過原始遞歸的規則定義的，因為它們不提供"無限迴圈"（未定義值）的機制。

範式定理

範式定理源於Kleene聲稱對於每個k有原始遞歸函數${\displaystyle U(y)\!}$和${\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}$使得對於任何k個自由變數的μ-遞歸函數${\displaystyle f(x_{1},\ldots ,x_{k})\!}$有一個e使得

${\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）。

例子

• 斐波那契數列
• 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.