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.