原始遞歸函數

在可計算性理論中，原始遞歸函數（英語：primitive recursive functions）對計算的完全的形式化而言是形成重要構造板塊的一類函數。它們使用遞歸和複合作為中心運算來定義，並且是遞歸函數的嚴格的子集，它們完全是可計算函數。通過補充允許偏函數和介入無界尋找運算可以定義出遞歸函數的更廣泛的類。

通常在數論中研究的很多函數，近似於實數值函數，比如加法、除法、階乘、指數，找到第 n 個質數等等是原始遞歸的（Brainerd and Landweber, 1974）。實際上，很難設計不是原始遞歸的函數，儘管某些函數是已知的(比如阿克曼函數)。所以，通過研究它們，我們能發現有廣泛影響的結論的那些性質。

原始遞歸函數可以用總是停機的圖靈機計算，而遞歸函數需要圖靈完全系統。

原始遞歸函數的集合在計算複雜性理論中叫做PR。

定義

原始遞歸函數接受自然數或自然數的元組作為參數並生成自然數。接受 n 個參數的函數叫做 n-元函數。基本原始遞歸函數用如下公理給出:

1. 常數函數: 0 元常數函數 0 是原始遞歸的。
2. 後繼函數: 1 元後繼函數 S，它接受一個參數並返回皮亞諾公理給出的後繼數，是原始遞歸的。
3. 投影函數: 對於所有 n≥1 和每個 1≤i≤n 的 i，n 元投影函數 P_iⁿ，它接受 n 個參數並返回它們中的第 i 個參數，是原始遞歸的。

更加複雜的遞歸函數可以通過應用下列公理給出的運算來獲得:

1. 複合: 給定k 元原始遞歸函數 f，和 k 個 m 元原始遞歸函數 g₁,...,g_k，f 和 g₁,...,g_k 的複合，也就是 m 元函數 h(x₁,...,x_m) = f(g₁(x₁,...,x_m),...,g_k(x₁,...,x_m)), 是原始遞歸的。
2. 原始遞歸: 給定 k 元原始遞歸函數 f，和 k+2 元原始遞歸函數 g，定義為 f 和 g 的原始遞歸的 k+1 元函數，也就是函數 h 這裏的 h(0,x₁,...,x_k) = f(x₁,...,x_k) 並且 h(S(n),x₁,...,x_k) = g(h(n,x₁,...,x_k),n,x₁,...,x_k), 是原始遞歸的。

服從這些公理的函數是原始遞歸的，如果它是上述基本函數之一，或者它可以通過應用有限次數的運算獲得自基本函數。

投影函數的作用

投影函數可用來避免採用上述明顯刻板的函數元數方式；通過使用各種投影函數的複合，有可能把一個函數的參數子集遞移到另一個函數。例如，如果 g 和 h 是二元原始遞歸函數，則

$f(a,b,c) = g(h(a,c),h(a,b)) \!$

也是原始遞歸的。使用投影函數的一個形式定義為

$f(a,b,c) = g(h(P^3_1(a,b,c),P^3_3(a,b,c)),h(P^3_1(a,b,c),P^3_2(a,b,c)))$.

轉換謂詞到數值函數

在某些設置中，自然的考慮接受混合了數值和真值{ t= true, f=false } 的參數，或生成真值作為輸出的原始遞歸函數(參見 Kleene [1952 pp.226–227])。這可以通過把真值辨識為任何固定方式的數值來完成。例如，通常把真值t 辨識為 1 和真值 f 辨識為 0。一旦作出這種辨識，集合 A 的特徵函數，它在文字上返回 1 或 0，可以被看作判定一個數是否在集合 A 中的謂詞。把謂詞辨識為數值函數的這種方式將假定於本文餘下部分。

例子

加法

直覺上我們會把加法遞歸的定義為:

add(0,x)=x

add(n+1,x)=add(n,x)+1

為了使它適合於嚴格的原始遞歸定義,我們定義:

add(0,x)=P₁¹(x)

add(S(n),x)=S(P₁³(add(n,x),n,x))

(注意: 這裏的 P₁³ 是一個函數，它接受 3 個參數並返回第一個。)

P₁¹ 是簡單的恆等函數；包含它是上述原始遞歸運算定義的要求；它扮演了 f 的角色。S 和 P₁³ 的複合，它是原始遞歸的，它扮演了 g 的角色。

減法

我們可以定義有限減法，就是說，截止到 0 的減法(因為我們還沒有負數的概念呢)。首先我們必須定義"前驅" 函數，它擔任後繼函數的對立物。

直覺上我們會把前驅定義為:

pred(0)=0

pred(n+1)=n

為了使它適合正式的原始遞歸定義，我們寫:

pred(0)=0

pred(S(n))=P₂²(pred(n),n)

現在我們以類似加法的方式定義減法。

sub(0,x)=P₁¹(x)

sub(S(n),x)=pred(P₁³(sub(n,x),n,x))

出於簡單的緣故，切換了"標準"定義的參數次序來適合原始遞歸的要求，就是說， sub(a,b) 對應於 b-a。這可以輕易的使用適當的投影來矯正。

很多類似的函數可以被證明是原始遞歸的；一些例子包括條件、指數、質數檢驗和數學歸納法，並且原始遞歸函數可以被擴充來運算在其他物件上比如整數和有理數。

在整數和有理數上的運算

通過使用哥德爾數，原始遞歸函數可以被擴充到在其他物件比如整數和有理數上的運算上。如果以標準方式編碼整數用哥德爾數，算術運算包括加法、減法、乘法都是原始遞歸的。類似的，如果以哥德爾數表示有理數，則域運算都是原始遞歸的。

與遞歸函數的聯系

通過介入無界尋找算子可定義更廣泛的偏遞歸函數類。這個算子的使用可以導致偏函數，就是說，對每個參數有最多一個值，但是不同於全函數，不必須對參數有值的關係(參見定義域)。一個等價的定義聲稱偏遞歸函數是可以被圖靈機就算的函數。全遞歸函數是對所有輸入有定義的偏遞歸函數。

所有原始遞歸函數都是全遞歸的，但不是所有全遞歸函數都是原始遞歸的。阿克曼函數 A(m,n)是周知的不是原始遞歸的全遞歸函數。原始遞歸函數有作為使用阿克曼函數的全遞歸函數的子集的一個特徵。這個特徵聲稱一個函數是原始遞歸的，當且僅當有一個自然數 m 使得這個函數可以被總在 A(m,n) 或更少步驟內停機的圖靈機計算，這裏的 n 是原始遞歸函數的參數的總數。

限制

原始遞歸函數意圖緊密對應於我們直覺上可計算函數應該的樣子。當然函數的初始集合在直覺上是可計算的(因為它們非常簡單)，而你能用來建立新原始遞歸函數的兩個運算也是非常直接的。但是原始遞歸函數的集合不包含所有可能的可計算函數 — 這可以看作康托爾對角論證法的變體。這個論證提供了一個不是原始遞歸的可計算函數。證明的梗概如下:

原始遞歸函數集合可以被計算列舉。這個編號方案在函數定義上是唯一的，儘管在實際函數自身上不是唯一的(因為所有的函數都可以有無限數目的定義 — 考慮簡單的由恆等函數構成)。這個編碼在可計算性的形式模型，比如遞歸函數或圖靈機下定義的意義上是可計算的，邱奇-圖靈論題涉及的任何機器都可以。

現在考慮一個矩陣，這裏的行是在這個編號方案下的有一個參數的原始遞歸函數，而列是自然數。則每個元素 (i, j) 對應於計算於數 j 之上的第 i 個一元原始遞歸函數。我們可以寫為 f_i(j)。

現在我們考慮函數 g(x) = S(f_x(x))。g 位於這個矩陣的對角線上，並簡單的對它找到的值加一。這個函數是可計算的(按上述定義)，但是明顯的沒有計算它的原始遞歸函數存在，因為它與每個可能的原始遞歸函數都有至少一個值不同。所以，必然存在不是原始遞歸的可計算函數。

這個論證可以應用於能用這種方式列舉的任何一類的可計算(全)函數上。所以，任何這種可計算(全)函數的明確列表都不可能是完全的，比如那些可以用總是停機的機器計算的函數。但是要注意，偏可計算函數集合(那些不需要對所有參數有定義的函數)可以被明確的列舉，例如通過列舉圖靈機編碼。

可以明確展示的一個簡單的 1-元可計算函數阿克曼函數，它是對任何自然數遞歸定義的，但不是原始遞歸的。

參考

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0471095850

參見

• 判定器

引用

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
• Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987. ISBN 0-387-15299-7
• Stephen Kleene (1952) Introduction to Metamathematics, North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint). In Chapter XI. General Recursive Functions §57
• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70–71.