原始遞歸函式

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

相關概念介紹

合成

設 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),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 。