原始遞歸函數

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

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

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

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

設 f 是 k 元部分函數，g1、g2、...、gk是 k 個n 元部分函數，令

h(x1,...,xn)=f(g1(x1,...,xn),...,gk(x1,...,xn))

稱函數h是由 f 和g1,...,gk 合成得到的。

1. 設 g 是2元全函數，k 是一個常數，函數 h 由下述等式給出

h(0)=k,

h(t+1)=g(t,h(t))

稱 h 是由 g 經過原始遞歸運算得到的。

2. 設 f 和 g 分別是 n 元和 n+2 元全函數， n+1 元函數 h 由下述等式給出

h(x1,...,xn,0)=f(x1,...,xn),

h(x1,...,xn,t+1)=g(t,h(x1,...,xn,t),x1,...,xn)

稱 h 是由 f 和 g 經過原始遞歸運算得到的。

包括：

後繼函數： s(x)=x+1

零函數： n(x)=0

投影函數： Ui n (x1,...,xn)=xi, 1≦i≦n

定義：

由 初始函數經過 有限次合成和原始遞歸得到的函數稱作 原始遞歸函數

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

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

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

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

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

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

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

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

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

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

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