PR (複雜度)

PR 是包含所有原始遞歸函數 – 或者換句話說，所有能被這類函數定義的形式語言，這包含了加法，乘法，指數，以及迭代冪次等等。

阿克曼函數則是一個並非 原始遞歸函數的範例，告訴我們R包含但不等同(strictly contain，或者說嚴格包含)PR。

PR 函數可以被獨立的列舉，而並非所有R裡面的函數皆可。這告訴我們'PR'有一個語意的定義，但是R則沒有。

另一方面，我們可以用下列的概念去使用原始遞歸函數"列舉"任何的遞歸可枚舉集合 (參見另一個複雜度類RE)：給定輸入 (M, k)，M是一個圖靈機而k是一個正整數，如果M會在k步以內停止則輸出M；否則就甚麼都不輸出。然後，這裡輸出的聯集，也就是(M, k)這些組合所有可能的輸出，恰好是會停止的M的集合。

PR 包含但不等於ELEMENTARY。

參考資料

• Complexity Zoo: PR.