遞迴函式

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

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

所有遞迴函式的集合叫做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.