在可計算性理論中，原始遞歸函式對計算的完全的形式化而言是形成重要構造板塊的一類函式。它們使用遞歸和複合作為中心運算來定義，並且是遞歸函式的嚴格的子集，它們是完全可計算函式。通過補充允許偏函式和介入無界查找運算可以定義出遞歸函式的更廣泛的類。
基本介紹
- 中文名：原始遞歸函式
- 外文名：primitive recursive function
- 後繼函式：s(x)=x+1
- 零函式：n(x)=0
簡介,介紹,合成,原始遞歸,定義,常用,與遞歸函式的聯繫,限制,
簡介
在可計算性理論中，原始遞歸函式（英語：primitive recursive functions）對計算的完全的形式化而言是形成重要構造板塊的一類函式。它們使用遞歸和複合作為中心運算來定義，並且是遞歸函式的嚴格的子集，它們完全是可計算函式。通過補充允許偏函式和介入無界查找運算可以定義出遞歸函式的更廣泛的類。
通常在數論中研究的很多函式，近似於實數值函式，比如加法、除法、階乘、指數，找到第n個素數等等是原始遞歸的（Brainerd and Landweber, 1974）。實際上，很難設計不是原始遞歸的函式，儘管某些函式是已知的(比如阿克曼函式)。所以，通過研究它們，我們能發現有廣泛影響的結論的那些性質。
介紹
合成
設 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
定義：
由 初始函式經過 有限次合成和原始遞歸得到的函式稱作 原始遞歸函式
常用
1. 常數K
2. x
3. x+y
4. x·y
5. x!
通常在數論中研究的很多函式，近似於實數值函式，比如加法、除法、階乘、指數，找到第 n個素數等等是原始遞歸的（Brainerd and Landweber, 1974）。實際上，很難設計不是原始遞歸的函式，儘管某些函式是已知的(比如阿克曼函式)。所以，通過研究它們，我們能發現有廣泛影響的結論的那些性質。
原始遞歸函式可以用總是停機的圖靈機計算，而遞歸函式需要圖靈完全系統。
原始遞歸函式的集合在計算複雜性理論中叫做 PR 。
與遞歸函式的聯繫
通過介入無界查找運算元可定義更廣泛的偏遞歸函式類。這個運算元的使用可以導致偏函式，就是說，對每個參數有最多一個值，但是不同於全函式，不必須對參數有值的關係(參見定義域)。一個等價的定義聲稱偏遞歸函式是可以被圖靈機就算的函式。全遞歸函式是對所有輸入有定義的偏遞歸函式。
所有原始遞歸函式都是全遞歸的，但不是所有全遞歸函式都是原始遞歸的。阿克曼函式A(m,n)是周知的不是原始遞歸的全遞歸函式。原始遞歸函式有作為使用阿克曼函式的全遞歸函式的子集的一個特徵。這個特徵聲稱一個函式是原始遞歸的，若且唯若有一個自然數m使得這個函式可以被總在 A(m,n) 或更少步驟內停機的圖靈機計算，這裡的n是原始遞歸函式的參數的總數。
限制
原始遞歸函式意圖緊密對應於我們直覺上可計算函式應該的樣子。當然函式的初始集合在直覺上是可計算的(因為它們非常簡單)，而你能用來建立新原始遞歸函式的兩個運算也是非常直接的。但是原始遞歸函式的集合不包含所有可能的可計算函式 — 這可以看作康拖爾對角論證法的變體。這個論證提供了一個不是原始遞歸的可計算函式。證明的梗概如下:
原始遞歸函式集合可以被計算枚舉。這個編號方案在函式定義上是唯一的，儘管在實際函式自身上不是唯一的(因為所有的函式都可以有無限數目的定義 — 考慮簡單的由恆等函式構成)。這個編碼在可計算性的形式模型，比如遞歸函式或圖靈機下定義的意義上是可計算的，邱奇-圖靈論題涉及的任何機器都可以。
現在考慮一個矩陣，這裡的行是在這個編號方案下的有一個參數的原始遞歸函式，而列是自然數。則每個元素 (i,j) 對應於計算於數j之上的第i個一元原始遞歸函式。我們可以寫為fi(j)。
現在我們考慮函式g(x) = S(fx(x))。g位於這個矩陣的對角線上，並簡單的對它找到的值加一。這個函式是可計算的(按上述定義)，但是明顯的沒有計算它的原始遞歸函式存在，因為它與每個可能的原始遞歸函式都有至少一個值不同。所以，必然存在不是原始遞歸的可計算函式。
這個論證可以套用於能用這種方式枚舉的任何一類的可計算(全)函式上。所以，任何這種可計算(全)函式的明確列表都不可能是完全的，比如那些可以用總是停機的機器計算的函式。但是要注意，偏可計算函式集合(那些不需要對所有參數有定義的函式)可以被明確的枚舉，例如通過枚舉圖靈機編碼。
可以明確展示的一個簡單的 1-元可計算函式阿克曼函式，它是對任何自然數遞歸定義的，但不是原始遞歸的。
