PR (複雜度) PR 是包含所有原始遞歸函數  或者換句話說所有能被這類函數定義的形式語言這包含了加法乘法指數以及迭代冪次等等 阿克曼函數則是一個並非 原始遞歸函數的範例告訴我們R包含但不等同strictly contain或者說嚴格包含PR PR 函數可以被獨立的列舉而並非所有R裡面的函數皆可這告訴我們PR有一個語意的定義但是R則沒有 另一方面我們可以用下列的概念去使用原始遞歸函數列舉任何的遞歸可枚舉集合 參見另一個複雜度類RE給定輸入 M kM是一個圖靈機而k是一個正整數如果M會在k步以內停止則輸出M否則就甚麼都不輸出然後這裡輸出的聯集也就是M k這些組合所有可能的輸出恰好是會停止的M的集合 PR 包含但不等於ELEMENTARY