PR (複雜度)

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

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

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

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

PR 包含但不等於ELEMENTARY

參考資料